Ngọt - 03 Hay Là

Hay là làm tí toán nhỉ ?

Cho dãy $A$ gồm $a_1,a_2,...,a_n$. Kí hiệu $S(k)$ là tổng của tích các dãy con (có thể không liên tiếp) độ dài $k\ (1\le k\le n)$.
Với một số nguyên $x$, các bạn hãy tính $M = x^n + x^{n-1}.S(1) +\dots\ + x^0.S(n)$

Input

• Dòng đầu tiên gồm $2$ số nguyên dương $n,x(1\le n\le 10^7,1\le x\le 10^{18})$.
• Dòng tiếp theo gồm $n$ số nguyên dương $a_1,a_2,...,a_n$. $(1\leq a_i\leq 10^{12})$

Output

• In ra $1$ dòng là kết quả của bài toán, do kết quả rất lớn nên hãy in ra sau khi chia lấy dư cho $10^9+7$

Subtasks

• Subtask $1$: Đảm bảo $n\leq 10$. ($5$ điểm)
• Subtask $2$: Không có ràng buộc gì thêm. ($95$ điểm)

Example

4 1
1 2 3 4

120