1153 - 有三项求和的递推
时间限制 : 1 秒
内存限制 : 128 MB
求递推公式f(n)=f(n-1)+2f(n-2)+3f(n-3)的第n项的值，其中f(1)=0，f(2)=1，f(3)=1. 该值会很大，输出f(n)模100000007的值。
输入
一个正整数n.
输出
f(n)模100000007的值。
样例
输入
4
输出
3
输入
10
输出
561
提示
对所有的数据,1<=n<=10000