跳楼梯

小华正在准备体育考试，他为跳远感到忧愁。老师建议他每天跳Ｎ级台阶，锻炼暴发力。为此，小华为自己制订了一项规则：

（１）当跳到偶数时，他可以跳２级或３级；

（２）当他跳到奇数时，他可以跳１级或４级；

请问，若刚开始时他处在０级，他跳到Ｎ级的方案数是多少？

Input

一行一个整数Ｎ。

Output

一行一个整数，表示跳到Ｎ级的方案数，最后的结果对（109+7）取模。

Sample Input

9 Sample Output

4

HINT

数据范围：

0<Ｎ<=5*107