题目描述

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

样例

样例 1

输入 # 1

0
2
3
10

输出 # 1

0
2
5
6497