eolymp
bolt
Try our new interface for solving problems
Problems

Bad Substring

Bad Substring

Time limit 1 second
Memory limit 128 MiB

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