PROG0269 - Fibonacci words

The term Fibonacci words is used to stipulate a row of words that are constructed in the same manner as the Fibonacci sequence:

  • the zeroth Fibonacci word is a
  • the first Fibonacci word is b
  • for $n > 1$, the $n$th Fibonacci word is built by merging the $(n-1)$th and $(n-2)$th Fibonacci word

Input

The input consists of a single line containing the number $n \in \mathbb{N}$.

Output

The output consists of a single line containing the $n$th Fibonacci word.

Example

Input:

1

Output:

b

Example

Input:

5

Output:

babbabab

De term Fibonacciwoorden wordt gebruikt voor een rij van woorden die op eenzelfde manier opgebouwd wordt als de getallenrij van Fibonacci:

  • het nulde Fibonacciwoord is a
  • het eerste Fibonacciwoord is b
  • voor $n > 1$ wordt het $n$-de Fibonacciwoord opgebouwd door het $(n-1)$-de en $(n-2)$-de Fibonacciwoord samen te nemen

Invoer

De invoer bestaat uit één regel die een getal $n \in \mathbb{N}$ bevat.

Uitvoer

De uitvoer bestaat uit één regel die het $n$-de Fibonacciwoord bevat.

Voorbeeld

Invoer:

1

Uitvoer:

b

Voorbeeld

Invoer:

5

Uitvoer:

babbabab

Added by:Peter Dawyndt
Date:2012-08-27
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:PY_NBC
Resource:None

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.