Competitions
Five for week 14 (2013-2014)
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 data
One number n (0 ≤ n ≤ 45).
Output data
Print the number of required strings.
Examples
Input example #1
0
Output example #1
1
Input example #2
3
Output example #2
21
Input example #3
11
Output example #3
46368