AmzMohammad is a novice problem setter in Spoj. for start of his work he decided to write a classical and sample problem. (for UI ACM summer program ) 

How many N-words (words with N letters) from the alphabet {0, 1, 2} are such that neighbors differ at most by 1? 

Input

A positive integer N.

Output

Number of N-words with told conditions.

Answer is less than 1000000000. it is the only constraint :)

Example

Input:
2

Output:
7