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
nadstratosfer: 2017-11-24 06:32:47

utkarshsingh99: Calculate how many n-digit numbers in base 3 are there such that the difference between any pair of adjacent digits is 0 or 1.

utkarshsingh99: 2017-11-22 22:54:44

Can anyone explain what exactly is the problem statement trying to say?

vengatesh15: 2017-03-27 09:42:28

easy dp...

vignesh294: 2016-12-20 13:52:59

@surajmall: The seven N-words for N=2 are: 00, 01, 11, 10, 12, 22, 21.

Last edit: 2016-12-20 13:57:56
surajmall: 2016-12-11 16:58:58

anyone can make me understand the given test case how output 7 come

sri: 2016-09-25 17:30:04

100th
nice dp!!!

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...

CounterNormalize: 2016-01-13 21:17:47

Last edit: 2016-01-13 21:18:01
raghav12345: 2016-01-12 10:35:40

very good question on dp


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