問題
フィボナッチ数列を拡張した数列を考える。
この数列を拡張フィボナッチ数列と呼ぶ。
拡張フィボナッチ数列${F_n}$は
$\displaystyle F_n = \begin{cases}
A & (n = 0) \\
B & (n = 1) \\
F_{n-1} + F_{n-2} & (n \geq 2)
\end{cases}$
と定義される。
n, A, Bが与えられるので、n番目の拡張フィボナッチ数を求めよ。
ただし、非常に大きな数になりうるので、1,000,000,007($10^9 + 7$) で割った余りを出力すること。
入力
n A B
出力
Fn
最後に改行をすること。
制約
$1 \leq n \leq 10^{18}$
$0 \leq A \leq 10^{9}$
$0 \leq B \leq 10^{9}$
入力はすべて整数。
テストケース
例1
入力
10 0 1
出力
55
これは普通のフィボナッチ数列である。
例2
入力
10 2 1
出力
123
これはリュカ数と呼ばれるものである。