問題文

正整数 $N,M$ と長さ $N-1$ の正整数列 $A=(A_2,A_3,\ldots,A_N)$ が与えられます。$A$ の添字が $2$ から始まることに注意してください。

このとき、以下の条件を満たす $N\times M$ 行列 $B$ を考えます。

• $1 \le j \le M$ を満たす任意の $j$ について、$B_{1,j}=0$
• $2 \le i \le N$ を満たす任意の $i$ について、$B_{i,1}=A_i$
• $2 \le i \le N$ , $2 \le j \le M$ を満たす任意の組 $(i,j)$ について、$B_{i,j}=B_{i-1,j}+B_{i,j-1}$

条件を満たす $B$ は一意に定まることが示せるので、 $\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{M} B_{i,j}$ を $10^9+7$ で割ったあまりを求めてください。

制約

• 入力はすべて整数
• $2 \le N \le 10^5$
• $2 \le M \le 10^{18}$
• $1 \le A_i \le 10^9\ (2 \le i \le N)$

入力

入力は以下の形式で標準入力から与えられます。

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

出力

答えを出力せよ。

入出力例1

4 2
1 2 3

16

入出力例2

2 200000
1

200000

入出力例3

4 141592
65 35 89

406519592