AMZSEQ - AMZ Word

no tags 

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

hide comments
hackerman97: 2016-03-28 19:30:47

Could be better if N was large

minhthai: 2016-01-21 05:51:55

don't think too much about math...

raghav12345: 2016-01-12 10:35:40

very good question on dp


Added by:mohammad mahmoodi
Date:2012-07-31
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:AmzMohammad ( Mohammad Mahmoodi )