Fibonacci strings generation

Generate $n$-th Fibonacci string that is defined with the next recurrent formula:

• $f(0)="a"$;

• $f(1)="b"$;

• $f(n)=f(n-1)+f(n-2)$, where $"+"$ operation means concatenation

For example, $f(3)=f(2)+f(1)=(f(1)+f(0))+f(1)="b"+"a"+"b"="bab"$.

Input

One integer $n(0\le n\le 20)$.

Output

Print the $n$-th Fibonacci string.

Examples