0933 - 擬:フィボナッチ数列

時間制限 1 秒 / メモリ制限 64 MB / 得点 1 / Writer ei1710 / x 28 / 統計 /

    タグ:

TLE
1sec
MLE
64MB
得点
1

問題

フィボナッチ数列とは、
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演算(あまりを求める)を表す。