問題文

非負整数 L に対し、レベル L のシェルピンスキーのガスケットとは次のような図形である。

• レベル 0 のシェルピンスキーのガスケットとは、 1 個の正三角形である。
• レベル i (i ≧ 1) のシェルピンスキーのガスケットは、レベル i-1 のシェルピンスキーのガスケットに含まれる 3^i-1 個の正三角形それぞれに対して以下の操作を行って得られる図形である。
  (操作) 正三角形の各辺の中点を結び、中心に小さな正三角形を作る。この正三角形を図形から取り除く（この結果、もとの正三角形は 3 つの小さな正三角形に分割される）。

以下にレベル 0,1,2,3,4 のシェルピンスキーのガスケットを図示する。

正整数 L が与えられる。レベル L のシェルピンスキーのガスケットに含まれる 3^L 個の正三角形のすべての辺を考える。これらの線分から形成される単純多角形 (自己交差しない多角形) の個数を 1,000,000,007 で割った余りを求めよ。相似な多角形であっても位置が異なるものは区別する。

以下に数えるべき多角形とそうでないものの例を示す。

入力例1

1

出力例1

11

以下の 11 個の単純多角形が存在する。

入力例2

2

出力例2

1033

入力例3

3

出力例3

30304092

入力例4

123

出力例4

853343829