斐波那契数列的简单升级

题目描述

斐波那契数列大家肯定耳熟能详了吧，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