Competitions

# 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 (0n20).

#### Output

Print the n-th Fibonacci string.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3

Output example #1
bab

Input example #2
5

Output example #2
babbabab

Author Mykhailo Medvediev