- Prepare
- Mathematics
- Combinatorics
- Tower 3-coloring

# Tower 3-coloring

# Tower 3-coloring

For a given integer , there is a tower built from blocks stacked vertically. Each of these blocks can be colored in different colors: red, green or blue. How many different colorings of the tower can be created? Two colorings are considered different if and only if there exists at least one block with different colors in the colorings. Since the result can be a huge number, apply a modulo on the result.

**Input Format**

The first line contains a single integer .

**Constraints**

**Output Format**

In a single line print a single integer denoting the number of different colorings of tower of the height calculated modulo .

**Sample Input 0**

```
1
```

**Sample Output 0**

```
27
```

**Explanation 0**

In the sample we have , so the tower has height . Each of these three blocks can be colored with any of available colors, so the total number of different colorings is .