# F005A. Paraules de Fibonacci P50726

Statement html

The words of Fibonacci F1, F2, F3, … are described in the following way:

• F1 = “a”.
• F2 = “b”.
• For every n ≥ 3, Fn is the result of concatenate Fn−2 with Fn−1.

The first seven words of the sequence of Fibonacci are: F1 = “a”, F2 = “b”, F3 = “ab”, F4 = “bab”, F5 = “abbab”, F6 = “bababbab” and F7 = “abbabbababbab”.

Your task is to write a program that, given a sequence of words, prints if they are Fibonacci words or they are not. For those that are it, you must indicate their position in the sequence.

Input

The input is a sequence of words only composed by the letters a and b. None of the words will have more than 1000 letters.

Output

For each Word, your program must indicate its position in the sequence, or print that it is not a word of Fibonacci, following the format of the instance.

Hint

Notice that the length of a word of Fibonacci increases very fast. Therefore, there are few words of Fibonacci having size 1000 or less (in fact, there are exactly 16). Calculate all of them at the beginning of the program.

Observations

• Remember that a string s with n characters c can be declared like this: string s(n, c);
• Remember also that the string operations like s += ’a’;, s1 += s2; or s = s1 + s2; are not allowed.
Public test cases
• Input

```a
b
ba
aaa
bb
bababbab
```

Output

```a is the word number 1
b is the word number 2
ba is not a Fibonacci word
aaa is not a Fibonacci word
bb is not a Fibonacci word
bababbab is the word number 6
```
• Information
Author
Professorat de P1
Language
English
Translator
Carlos Molina
Original language
Catalan
Other languages
Catalan
Official solutions
C++
User solutions
C++ Python