055 - Recurrence Formula 1
Editorial
/
Time Limit: 1 sec / Memory Limit: 1024 MB
配点 : 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 で割った余りを求めることに注意してください。