054 - Fibonacci Hard (mod 1000000000)
解説
/
実行時間制限: 1 sec / メモリ制限: 1024 MB
配点 : 1000 点
問題文
以下の漸化式で定められるフィボナッチ数列の第 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 は整数
入力
入力は以下の形式で標準入力から与えられます。
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 で割った余りを求めることに注意してください。