問題一覧 > 通常問題

No.1489 Repeat Cumulative Sum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 52
作問者 : turtle0123turtle0123 / テスター : magstamagsta
4 ProblemId : 6229 / 出題時の順位表
問題文最終更新日: 2021-04-23 23:20:45

問題文

$2$ 以上の正整数 $N,M$ と長さ $N-1$ の正整数列 $A$ が与えられます。$A$ の添字が2から始まることに注意してください。

ここで、行列 $B$ は $N$ 行 $M$ 列であり、下記を満たしています。

  • $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}$

このときの $\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{M} B_{i,j}$ を求め、答えを $10^9+7$ で割ったあまりを $0$ 以上 $10^9+6$ 以下の整数で出力してください。

(行列 $B$ の $i$ 行目 $j$ 列目の値を $B_{i,j}$ と表記しています。)

制約

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

入力

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

$\large N$ $\large M$
$\large A_2$ $\large A_3$ $\large A_4$ $\large \cdots$ $\large A_N$

出力

答えを $10^9+7$ で割ったあまりを $0$ 以上 $10^9+6$ 以下の整数で $1$ 行に出力し、最後に改行してください。

入出力例1


入力例1

4 2
1 2 3

出力例1

16

$B_{1,1}=0,B_{1,2}=0,B_{2,1}=1,B_{2,2}=1,B_{3,1}=2,B_{3,2}=3,B_{4,1}=3,B_{4,2}=6$ より、$\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{M} B_{i,j}=16$ です。

入出力例2


入力例2

2 200000
1

出力例2

200000

入出力例3


入力例3

4 141592
65 35 89

出力例3

406519592

$10^9+7$ で割ったあまりを求めることに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。