← 返回题目列表

AtCoder · math_and_algorithm_av

056. 递归公式 2

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

配点 : 1000 点

問題文

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

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

另外,这样的序列 (a_1, a_2, a_3, \cdots) 称为 Tribonacci 序列。

制約

  • 4 \le N \le 10^{18}
  • N 是整数

入力

输入是按以下格式从标准输入给出的。 逐行打印

N

出力

请打印答案。


入力例 1

10

出力例 1

149

a=(1, 1, 2, 4, 7, 13, 24, 44, 81, 149) 和 10 部分是 请注意,我们正在寻找除以 149 。


入力例 2

876543210987654321

出力例 2

639479200

10^9+7 时的余数。