题目描述

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