Fibonacci words are defined similarly to Fibonacci numbers:  
    FIB₁ = b     FIB₂ = a     FIB_k+2 = FIB_k+1*FIB_k for k >= 1,
where * denotes operation of connecting words (concatenation). 

Hence we have:
FIB₃ = ab;     FIB₄ = aba;     FIB₅ = abaab;     FIB₆ = abaababa.

Task

• reads from the text file FIB.IN a word comprising at least one and at most 30 characters a or b, and one positive integer n <= 200,
• computes how many times the word appears in the n-th Fibonacci word FIB_n (how many fragments of FIB_n are the same as the given word; the fragments may partially overlap).
• writes the result in the text file FIB.OUT.

Input

Output

Example

In the output file FIB.OUT should be written one integer:
3

Your program should look for the file FIB.IN in the current directory and produce the output file FIB.OUT in the current directory too. The file containing the source code of your program should have a name FIB.???, whereas you should put three-letter abbreviation of the used programming language name instead of ???. The same program in executable form should be written in the file FIB.EXE