Alice has an array $a_0a_1...a_{n-1}$, she want to calculate the other array $b_0b_1...b_{n-1}$ where
$b_i=\sum_{\text{max}(i_1,i_2,...,i_m)=i\ 0\leq i_j<n,\ j=1...m} a_{i_1}\times a_{i_2}\times \cdots \times a_{i_m}$.
Can you help her? For simplicity, please output $\sum_{i=0}^{n-1} (i+1)\cdot b_i \bmod\ 1,000,000,007$.

In the first line there are two integer $n, m\ (1 \leq n \leq 100,000,\ 1 \leq m \leq 1,000,000,000)$.
In the second line there are $n$ integers $a_0,a_1,...,a_{n-1}\ (1 \leq a_i \leq 1,000,000,000)$.

Output a single integer, which is $\sum_{i=0}^{n-1} (i+1)\cdot b_i \bmod\ 1,000,000,007$.

4985

$b_0=a_0⋅a_0=1$
$b_1 = a_0\cdot a_1 + a_1\cdot a_0 + a_1\cdot a_1= 120$
$b_2 = a_0\cdot a_2 + a_1\cdot a_2 + a_2\cdot a_0 + a_2\cdot a_1 + a_2\cdot a_2 = 168$
$b_3 = a_0\cdot a_3 + a_1\cdot a_3 + a_2\cdot a_3 + a_3\cdot a_0 + a_3\cdot a_1 + a_3\cdot a_2 + a_3\cdot a_3 = 440$
$b_4 = a_0\cdot a_4 + a_1\cdot a_4 + a_2\cdot a_4 + a_3\cdot a_4 + a_4\cdot a_0 + a_4\cdot a_1 + a_4\cdot a_2 + a_4\cdot a_3 + a_4\cdot a_4 = 496$
ans = $1\cdot b_0 + 2\cdot b_1 + 3\cdot b_2 + 4\cdot b_3 + 5\cdot b_4 = 4985$