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"$.
\InputFile
One integer $n~(0 \le n \le 45)$.
\OutputFile
Print the number of required strings.
Input example #1
1
Output example #1
3
Input example #2
3
Output example #2
21