游客 Signup | Login
中文 | En

2485 - I

通过次数

0

提交次数

0

Time Limit : 5 秒 Memory Limit : 128 MB

定义函数f(n)如下:

define mod 1000000007

int f(int n){
   if(n<3) return n;
   return (2f(n-1)+f(n-2)+3f(n-3))%mod;
}
求f(n)的值。

Input

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

<br />

Output

输出f(n)的值

Examples

Input Format

0
2
3
10

Output Format

0
2
5
6497