有三项求和的递推

题目描述

求递推公式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的值。

样例

提示

对所有的数据,1<= n <=10000