How many n-digit numbers can be created using only digits 5 and 9, where no three identical digits stand side by side?

Input

One number n (n ≤ 30).

Output

The amount of n-digit numbers.