I

题目描述

定义函数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)的值。

输入说明

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

输出说明

输出f(n)的值

样例

输入

0
2
3
10

输出

0
2
5
6497