After hearing all the wonderful things about the TTC subway, you are finally splurging $11.50 (that's an hour's pay!) on a day pass so you can spend your beautiful sunny Saturday *"Riding the Rocket"* in dark tunnels. This calls for some planning!

You have a map, which looks like four equilateral "triangles" glued together (you're terrible at drawing triangles, so you draw squares that look like a triangle when glued together instead).

Your map ends up looking like something below (the triangles have "side length" in this case).

With this map, you have effectively divided Toronto into square-shaped sectors! You know the subway system of Toronto has two *very* special properties — all subway lines cross exactly one edge between two square-shaped sectors! Also, each sector belongs to exactly one subway line. Therefore, there are two sectors joined by an edge in a single subway line.

You don't know the exact layout of the subway lines, and you're too lazy to go online and search it up. Therefore, you have adopted the foolproof strategy of drawing out *all* possible subway configurations for a map made up of equilateral triangles of side length . Two configurations are different if any two sectors are joined by a subway line in one configuration, but they are not in the other. How many configurations do you have to draw? Since this number may be very large, output it modulo (, a prime number).

#### Constraints

##### Subtask 1 [30%]

##### Subtask 2 [70%]

#### Sample Input

`1`

#### Sample Output

`2`

#### Explanation of Output for Sample Input

The two possible subway configurations (subway lines numbered for your convenience, same number indicates part of the same line):

```
1 1
1 2 2 1
2 2
```

## Comments

Why is

2

2 1

1

for the sample case not valid?

because it's the same thing as the first in the sample output

Are subway lines allowed to stop without reaching the other end of the map?

Subway lines only consist of two "adjacent" squares.

So you can't have them span >3 squares?

Nope.

Are the sectors the big thing(approximation of a square), or the individual "pixels" of the triangles?

The "pixels".