← 返回题目列表

AtCoder · arc037_d

D. 混沌多边形

中文机器翻译题面 查看原题

問題文

非負整数 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