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