問題一覧 > 通常問題

No.1489 Repeat Cumulative Sum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 70
作問者 : ytqm3ytqm3 / テスター : magstamagsta
4 ProblemId : 6229 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-16 18:52:05

問題文

正整数 N,M と長さ N1 の正整数列 A=(A2,A3,,AN) が与えられます。A の添字が 2 から始まることに注意してください。

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

  • 1jM を満たす任意の j について、B1,j=0
  • 2iN を満たす任意の i について、Bi,1=Ai
  • 2iN , 2jM を満たす任意の組 (i,j) について、Bi,j=Bi1,j+Bi,j1

条件を満たす B は一意に定まることが示せるので、 i=1Nj=1MBi,j109+7 で割ったあまりを求めてください。

制約

  • 入力はすべて整数
  • 2N105
  • 2M1018
  • 1Ai109 (2iN)

入力

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

N M
A2 A3  AN

出力

答えを出力せよ。

入出力例1


入力例1

4 2
1 2 3

出力例1

16

B1,1=0,B1,2=0,B2,1=1,B2,2=1,B3,1=2,B3,2=3,B4,1=3,B4,2=6 より、i=1Nj=1MBi,j=16 です。

入出力例2


入力例2

2 200000
1

出力例2

200000

入出力例3


入力例3

4 141592
65 35 89

出力例3

406519592

109+7 で割ったあまりを求めることをお忘れなく。

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