Problem Statement

You are given positive integers $N,M$ and a sequence of positive integers $A=(A_2,A_3,\ldots,A_N)$ of length $N-1$. Note that the indices of $A$ start from $2$.

Consider an $N\times M$ matrix $B$ satisfying the following conditions.

• For every $j$ satisfying $1 \le j \le M$, $B_{1,j}=0$
• For every $i$ satisfying $2 \le i \le N$, $B_{i,1}=A_i$
• For every pair $(i,j)$ satisfying $2 \le i \le N$ , $2 \le j \le M$, $B_{i,j}=B_{i-1,j}+B_{i,j-1}$

It can be shown that the $B$ satisfying the conditions is uniquely determined. Find $\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{M} B_{i,j}$ modulo $10^9+7$.

Constraints

• All input values are integers.
• $2 \le N \le 10^5$
• $2 \le M \le 10^{18}$
• $1 \le A_i \le 10^9\ (2 \le i \le N)$

Input

The input is given from standard input in the following format.

$N$ $M$
$A_2$ $A_3$ $\ldots$ $A_N$

Output

Output the answer.

Sample 1

4 2
1 2 3

16

Sample 2

2 200000
1

200000

Sample 3

4 141592
65 35 89

406519592