当前没有测试数据。

题目背景

小符同学在备战上半年的 ICPC 邀请赛。在研究递归算法时，他发现了一个递推规律非常有趣的“奇怪数列”。为了测试递归函数的执行效率，他决定写一个基础程序来计算它。

题目描述

给定一个数列 $f(n)$，其定义如下：

• 当 $n = 1$ 时，$f(1) = 1$
• 当 $n = 2$ 时，$f(2) = 2$
• 当 $n > 2$ 时，$f(n) = 2f(n-1) + 3f(n-2)$

请你编写一个递归程序，求出该数列第 $N$ 项对 $1000000007$ 取模后的值。

输入格式

输入一个正整数 $N$。

输出格式

输出一个整数，表示 $f(N) \pmod{1000000007}$ 的结果。

数据范围

对于 100% 的数据，$1 \leq N \leq 25$。

样例

3

7

5

61