描述

川草开始写高数作业啦,但是作业太多以至于不能一口气完成。

第一页和第二页都需要 1 个小时去写,因为题目越来越难所以川草写第 n 页所需的时间是第 n-1 页的时间加上三倍第 n-2 页的时间。

但是川草写完每页作业都会花一小时来编代码(计入作业时间)。

比如,第一页川草需要 2 小时(1小时作业+1小时代码),第二页也是 2 小时,第三页是 9 小时(2(第二页)+2(第一页)*3+1)。

那么请问川草完成第 n 页作业需要几小时(由于数量太大,我们将结果模上10^9 + 7)

输入格式

程序需要读入多个测试样例,每个测试样例中:

一个整数 n,表示完成第 n 页作业

输出格式

对每个测试样例:

一个整数,表示完成第 n 页作业需要的时间模上 10^9 + 7 的结果

样例输入

1
2
3
4

样例输出

2
2
9
16

数据范围

对于 30% 的数据:0 < n <= 100 对于 60% 的数据:0 < n <= 10^6 对于 100% 的数据:0 < n <= 10^18

资源约定

峰值内存消耗 < 256M

CPU消耗 < 5000ms


请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。

所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。

[C]

注意: main函数需要返回0

注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。

注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>, 不能通过工程设置而省略常用头文件。

[Java]

注意:不要使用package语句。不要使用jdk1.7及以上版本的特性。

注意:主类的名字必须是:Main,否则按无效代码处理。

Author

imcmy