Gardener has to paint trees after planting. He has paint of three colour: white, blue and orange.

How many ways he can paint of $N$ trees, if not any two the same colours can be side by side?

Input

The quantity of trees is $N$$(1 ≤ N ≤ 50)$.

Output

The quantity of ways of paint.