Bad Substring

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

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

Input

One integer $n (0 \leq n \leq 45)$ .

Print the number of required strings.

Input #1

Answer #1

Input #2

Answer #2

Submissions 4K

Acceptance rate 48%