Problem Description

For a non-negative integer $ L $, the level $ L $ Sierpinski gasket is defined as follows:

• The level $ 0 $ Sierpinski gasket is a single equilateral triangle.
• The level $ i $ ($i \geq 1$) Sierpinski gasket is obtained by performing the following operation on each of the $ 3i-1 $ equilateral triangles contained in the level $ i-1 $ Sierpinski gasket:
  (Operation) Connect the midpoints of each side of the equilateral triangle to form a smaller equilateral triangle in the center. Remove this smaller triangle (as a result, the original triangle is divided into three smaller equilateral triangles).

The following figures show the level $ 0, 1, 2, 3, 4 $ Sierpinski gaskets.

Given a positive integer $ L $, consider all the edges of the $ 3L $ equilateral triangles contained in the level $ L $ Sierpinski gasket. Find the number of simple polygons (polygons that do not self-intersect) formed by these line segments, modulo $ 1,000,000,007 $. Distinguish between similar polygons that have different positions.

The following examples illustrate what polygons should be counted and what should not.

Input Format

The input is given from the standard input in the following format:

$ L $

• The first line contains an integer $ L $ ($1 \leq L \leq 10^5$).

Output Format

Output the number of polygons modulo $ 1,000,000,007 $ to the standard output, followed by a newline.

Sample Input and Output

Sample Input #1

1

Sample Output #1

11

Sample Input #2

2

Sample Output #2

1033

Sample Input #3

3

Sample Output #3

30304092

Sample Input #4

123

Sample Output #4

853343829

Notes/Hints

Sample Explanation 1

There are $ 11 $ simple polygons as shown below. 

见题面 Input 部分

见题面 Output 部分