← 返回题目列表

AtCoder · math_and_algorithm_au

055. 递归公式 1

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

配点 : 1000 点

問題文

由下面的递推公式定义的序列号为 N 項 a_N 在 1000000007(=10^9+7) 求余数。

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

制約

  • 3 \le N \le 10^{18}
  • N 是一个整数

入力

输入以以下格式从标准输入提供。

N

出力

请打印答案。


入力例 1

10

出力例 1

1393

a=(1, 1, 3, 7, 17, 41, 99, 239, 577, 1393, ...) 和 10 部分是 请注意,我们正在寻找除以 1393 。


入力例 2

876543210987654321

出力例 2

841102483

10^9+7 时的余数。