← 返回题目列表

AtCoder · math_and_algorithm_at

054. 斐波那契硬线 (mod 1000000000)

中文机器翻译题面 查看原题

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