問題文
非負整数 L ,级别 L Sierpinski 的垫圈具有以下形状。
- 等级 什么是 0 Sierpinski 垫片? 1 等边三角形。
- 等级
什么是 i (i ≧ 1) Sierpinski 垫圈处于水平状态
包含在 i-1 Sierpinski 垫片中
该数字是通过对每个 3i-1 等边三角形执行以下操作获得的。
(操作)连接等边三角形每条边的中点,在中心创建一个小等边三角形。从图中去掉这个等边三角形(结果原来的等边三角形就变成了 3 分为两个小等边三角形)。
级别低于 图中显示了 0,1,2,3,4 的 Sierpinski 垫圈。 给出了

正整数 L 。水平 考虑 L Sierpinski 垫片中 该数字是通过对每个 3L 等边三角形的所有边。由这些线段形成的简单多边形(非自相交多边形)的数量为 除以 1,000,000,007 求余数。区分相似但位置不同的多边形。
下面显示了应该和不应该计算的多边形的示例。

入力
输入将以以下格式从标准输入给出。
L
- 1 行中,一个整数 L (1 ≦ L ≦ 105)。 来自行
出力
标准输出所需的多边形数量为 打印除以 1,000,000,007 后的余数并在末尾换行。
入力例1
1
出力例1
11
下面 有 11 简单多边形。

入力例2
2
出力例2
1033
入力例3
3
出力例3
30304092
入力例4
123
出力例4
853343829