問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 134
作問者 : trineutrontrineutron / テスター : QCFiumQCFium
0 ProblemId : 3068 / 出題時の順位表
問題文最終更新日: 2019-07-22 23:24:47

問題文

$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

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