Problems
Bad Substring
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 integer n~(0 \le n \le 45).
Output data
Print the number of required strings.
Examples
Input example #1
1
Output example #1
3
Input example #2
3
Output example #2
21