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

問題

フィボナッチ数列とは、
F₀ = 0
F₁ = 1
F_n = F_n-1 + F_n-2
と定義された数列です。

簡単に言うと、0番目のフィボナッチ数は0, 1番目のフィボナッチ数は1, n番目のフィボナッチ数はn-1番目のフィボナッチ数とn-2番目のフィボナッチ数の合計というわけです。

n番目のフィボナッチ数を求め、1000000007(10^9+7)で割ったあまりを出力するプログラムを作ってください。

ただし、今回はF₀,F₁を入力によって決定するものとします。

入力

 n F0 F1

1行にn,F₀,F₁が与えられる。

出力

n番目のフィボナッチ数を10^9+7で割ったあまりを1行に出力せよ。

制約

すべての入出力ケースにおいて以下を満たす。

• 0 ≦ n ≦ 1000
• 0 ≦ F₀, F₁ ≦ 10⁹

入出力例

入力1

4 0 1

出力1

3

入力2

33 4 33

出力2

125024310

hint

(A + B) % C = (A % C + B % C) % C

ここで、'%'はMOD演算(あまりを求める)を表す。