No.891 隣接3項間の漸化式

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 109
作問者 : trineutrontrineutron / テスター : QCFiumQCFium
0 ProblemId : 3068 / 出題時の順位表

問題文

$a, b, n$を$0$以上$10^9+7$未満の整数とする。$x_0=0, x_1=1, x_{i+2}=ax_{i+1}+bx_i (i \ge 0)$とするとき、$x_n$を$10^9+7$で割った余りを求めよ。

入力

$a\ b\ n$

入力は全て整数
$0 \le a, b, n \lt 10^9+7$

出力

$x_n$を$10^9+7$で割った余りを改行付きで出力してください。

サンプル

サンプル1
入力
1 1 10
出力
55

サンプル2
入力
10 10 10
出力
30499986

サンプル3
入力
1000000000 0 100
出力
7642709

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。