1102: 拼图
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：5
Solved：1
Description
小航最近迷上了拼图，有这么三种类型的拼图，分别为I型（大小为2个单位面积）、L型（大小为3个单位面积）和大L型（大小为4个单位面积），分别如下图所示：
同时，小航有一块面积大小为2×N的画布，画布由2×N个1×1区域构成。
小航需要用以上3种拼图将画布拼满，他想知道总共有多少种不同的方式?
拼图可以任意旋转，且画布的方向固定。
同时，小航有一块面积大小为2×N的画布，画布由2×N个1×1区域构成。
小航需要用以上3种拼图将画布拼满，他想知道总共有多少种不同的方式?
拼图可以任意旋转，且画布的方向固定。
Input
一个数字N，表示画布大小为2 × N。
Output
一个数字表示总共有多少种不同的方式将画布拼满，结果可能会很大，请将结果对1000000007取模后输出。
Sample Input Copy
3Sample Output Copy
9HINT
1<=N<=10000
输出结果记得要对1000000007取模。
输出结果记得要对1000000007取模。