该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

时间限制：1 Sec 内存限制：256 MB 输入文件：fib.in 输出文件：fib.out

给定整数 $n$，请计算 $X = \mathrm{fib}(\mathrm{fib}(n)) \bmod (10^9+7)$ 并输出结果。

其中，$\mathrm{fib}(n)$ 表示第 $n$ 个斐波那契数，满足以下要求：

$\mathrm{fib}(0)=0$，$\mathrm{fib}(1)=1$，对于 $i \gt 1$，$\mathrm{fib}(i)=\mathrm{fib}(i-1)+\mathrm{fib}(i-2)$。

输入格式

一个整数 $n$。

输出格式

一个整数，表示答案。

样例

样例 1

7

233

样例说明：

$\mathrm{fib}(7)=13$，$\mathrm{fib}(13)=233$。

样例 2

0

0

样例 3

1000000000000000000

279478839

数据范围

对于 12% 的数据，$n \le 20$。

对于 36% 的数据，$n \le 80$。

对于 100% 的数据，$0 \le n \le 10^{18}$。