問題
フィボナッチ数列とは、
F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2
と定義された数列です。
簡単に言うと、0番目のフィボナッチ数は0, 1番目のフィボナッチ数は1, n番目のフィボナッチ数はn-1番目のフィボナッチ数とn-2番目のフィボナッチ数の合計というわけです。
n番目のフィボナッチ数を求め、1000000007(10^9+7)で割ったあまりを出力するプログラムを作ってください。
ただし、今回はF0,F1を入力によって決定するものとします。
入力
n F0 F1
1行にn,F0,F1が与えられる。
出力
n番目のフィボナッチ数を10^9+7で割ったあまりを1行に出力せよ。
制約
すべての入出力ケースにおいて以下を満たす。
- 0 ≦ n ≦ 1000
- 0 ≦ F0, F1 ≦ 109
入出力例
入力1
4 0 1
出力1
3
入力2
33 4 33
出力2
125024310
hint
(A + B) % C = (A % C + B % C) % C
ここで、'%'はMOD演算(あまりを求める)を表す。