The gardener has planted N trees in one row. After planting the trees, the gardener needs to paint them. He has three colors of paint at his disposal: white, blue and orange. How many ways does he have to color trees if no two neighboring trees can be painted the same color?
Input
The only line contains one natural number - the number of trees N (1 ≤ N ≤ 50).
Output
In a single line, you need to output one number - the number of ways to paint.