配点 : 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 时的余数。