No.978 Fibonacci Convolution Easy

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 178
作問者 : keymoonkeymoon / テスター : tarattata1tarattata1
3 ProblemId : 3209 / 出題時の順位表
問題文最終更新日: 2020-01-30 13:22:00

問題文

数列 $a$ を $a_1=0,a_2=1,a_{n}=p \cdot a_{n-1} + a_{n-2}(3 \leq n)$ で定義します。
このとき、 $\sum_{i=1}^N\sum_{j=1}^i a_i \cdot a_j$ を $1000000007$ で割った余りを計算してください。

入力

$N\ p$
  • $1 \leq N \leq 2 \cdot 10^6$
  • $1 \leq p \leq 10^9$
  • 入力は全て整数である。

出力

$\sum_{i=1}^N\sum_{j=1}^i a_i \cdot a_j$ を $1000000007$ で割った余りを出力してください。最後に改行してください。

サンプル

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

数列 $a$ は $0\ 1\ 3\ 10 \cdots$ と続きます。 ここで求めるべきは $a_1 \cdot a_1 + a_2 \cdot a_1 + a_2 \cdot a_2 + a_3 \cdot a_1 + a_3 \cdot a_2 + a_3 \cdot a_3$ なので、 $0 + 0 + 1 + 0 + 3 + 9 = 13$ となります。

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

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