No.15 掛け算フィボナッチ

時間制限:$2.0sec$ / メモリ制限:$256MB$

問題文

こたまねぎ君はフィボナッチ数列のQ番目までの数字を全て掛け算するという問題を思いつきました。

ここでフィボナッチ数列は、$A[q] = A[q-1] + A[q-2](A[1] = 1,A[2] = 1)$という式で表されます。

10番目までの数字は、$1,1,2,3,5,8,13,21,34,55$です。

作問で忙しいこたまねぎ君の代わりに答えを出すプログラムを作成してください。

制約

• $1 ≦ Q ≦ 100000$

入力形式

入力は以下の形式で標準入力から与えられる。

Q

出力

フィボナッチ数列のQ番目までの数字を全て掛け算し、$1000000007$で割った余りを出力してください。

入出力例

4

6

$1 \times 1 \times 2 \times 3 = 6$です。

29182

454537974

$1000000007$で割った余りを出力する事に気を付けましょう。