Fibonacci Words

Memory limit: 32 MB

Fibonacci words are defined similarly to Fibonacci numbers:

,

where denotes operation of connecting words (concatenation).

Hence we have: , , , .

Task

Write a program that:

• reads from the standard input a word comprising at least one and at most characters or , and one positive integer (),
• computes how many times the word appears in the -th Fibonacci word (how many fragments of are the same as the given word; the fragments may partially overlap),
• writes the result to the standard output.

Input

In the first line of the standard input there is written one word. The word is composed of at least one and at most characters or . In the second line there is written one positive integer .

Output

In the standard output there should be written one nonnegative integer. It should be equal to the number of times the given word appears in the Fibonacci word .

Example

For the input data:

aba
6

the correct result is:

3

Task author: Wojciech Rytter.