問題文

以下の漸化式で定められる数列の第 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) をトリボナッチ数列といいます。

制約

• 4 \le N \le 10^{18}
• 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 で割った余りを求めることに注意してください。