问题 C: 上海市2024年1月月赛-丙组-T3-三排地砖

问题 C: 上海市2024年1月月赛-丙组-T3-三排地砖

时间限制: 1 Sec  内存限制: 128 MB
提交: 37  解决: 15
[提交] [状态] [讨论版] [命题人:]

题目描述

有一条道路需要铺设地砖，这条道路由n×3个方格组成。只有一种规格的地砖，大小是
1×2规格的，也就是恰好可以覆盖两个方格。请计算有多少种方法，将这条道路铺满地砖。
由于方案数可能很大，输出它模1,000, 000,007的余数即可。

输入

单个整数:表示n。(保证n为偶数)
1<=n<=200000

输出

单个整数:表示方案数模1, 000,000,007的余数。

样例输入 Copy 

2

样例输出 Copy 

3

提示

更多样例：
输入为4时，输出为11
输入为6时，输出为41
输入为8时，输出为153
[提交][状态]