問題一覧 > 通常問題

No.978 Fibonacci Convolution Easy

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 249
作問者 : keymoon / テスター : tarattata1
3 ProblemId : 3209 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-01-30 13:22:00

問題文

数列 a を a1=0,a2=1,an=p⋅an−1+an−2(3≤n) で定義します。
このとき、 ∑i=1N∑j=1iai⋅aj を 1000000007 で割った余りを計算してください。

入力

N p
  • 1≤N≤2⋅106
  • 1≤p≤109
  • 入力は全て整数である。

出力

∑i=1N∑j=1iai⋅aj を 1000000007 で割った余りを出力してください。最後に改行してください。

サンプル

サンプル1
入力
3 3
出力
13

数列 a は 0 1 3 10⋯ と続きます。 ここで求めるべきは a1⋅a1+a2⋅a1+a2⋅a2+a3⋅a1+a3⋅a2+a3⋅a3 なので、 0+0+1+0+3+9=13 となります。

サンプル2
入力
10 4
出力
370564556
サンプル3
入力
314159 265358979
出力
786063776

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