eolymp
Competitions

October 7 - BMTK Programming School, High League

Bad Substring

Find the number of strings of length n consisting of only the characters 'a', 'b' and 'c', not containing the substring "ab".

Input

One number n (0n45).

Output

Print the number of required strings.

Time limit 1 second
Memory limit 128 MiB
Input example #1
0
Output example #1
1
Input example #2
3
Output example #2
21
Input example #3
11
Output example #3
46368