说明

定义函数f(n)如下：
#define mod 1000000007
int f(int n){
   if(n<3) return n;
   return (2*f(n-1)+f(n-2)+3*f(n-3))%mod;
}
求f(n)的值。

输入格式

多组数据，每组输入n (0<=n<10^123)

输出格式

输出f(n)的值

0
2
3
10

0
2
5
6497

来源

输入输出练习 洛谷