题目描述

定义斐波那契数列 $\{a_n\}$：

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

请你输出第 $N$ 项 $a_N$ 对 $10^9$ 取模后的值。

输入格式

一行一个整数 $N$。 $3 \le N \le 10^{18}$

输出格式

输出一个整数，表示 $a_N \bmod 10^9$。

10

55