We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Combinatorics
  4. 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 .