说明

斐波那契数列大家肯定耳熟能详了吧，F（n）=F(n-1)+F(n-2)，n>=3,这里我们定义F(1)=F(2)=1,如果只要求F（n）,是不是显得太水了，目测是的，所以我们现在来求一求SUM=[F（1）]^4+[F(2)]^4+....[F(n)]^4的值，当然1<=n<=10^9，所以结果很大，要对10^9+7取余。雯神说“为什么不是求sigma(F[i]^我体重)呢？oh，it's too big”

Ps:[F(i)]^4代表F(i)的4次方。

输入格式

输入一个数n,当n=0时程序结束

输出格式

输出SUM%(10^9+7)的值

1
2
3
0

1
2
18

来源