题目描述

求 $f_1^2+f_2^2+f_3^2+....+f_n^2$ ， 其中 $f_i$ 代表斐波那契数列的第 $i$ 项。 $(f_0=0 , f_1=1)$

当然结果会很大，请将它对 $10^9+7$ 取模。

输入格式

一行一个数 $n$.

输出格式

一行一个数，代表答案。

样例

input

6

output

104

数据范围与提示

对于 $30\%$ 的数据，$n\leq 10^5$。
对于另外 $20\%$ 的数据，$n$ 是 $10^6$ 的倍数，且 $n\leq 5×10^9$。
对于 $100\%$ 的数据，$n\leq10^{18}$。