問題文

以下の漸化式で定められるフィボナッチ数列の第 N 項 a_N を 10^9 で割った余りを出力してください。

• a_1 = 1, a_2 = 1
• a_n = a_{n-1} + a_{n-2} (n \geq 3)

なお、書籍の問題文中では「下 9 桁」となっていますが、桁のはじめのゼロは取って出力してください。例えば a_N = 1012345678 の場合、012345678 ではなく 12345678 という出力が正解となります。

制約

• 3 \le N \le 10^{18}
• N は整数

入力例 1

10

出力例 1

55

フィボナッチ数列は a=(1,1,2,3,5,8,13,21,34,55,\dots) であり、第 10 項は 55 です。

入力例 2

876543210987654321

出力例 2

942619746

10^9 で割った余りを求めることに注意してください。