12943: 斐波那契数列的简单升级
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：Imported
Submit：1
Solved：0
Description
斐波那契数列大家肯定耳熟能详了吧，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次方。
Input
输入一个数n,当n=0时程序结束
Output
输出SUM%(10^9+7)的值
Sample Input Copy
1
2
3
0
Sample Output Copy
1
2
18