시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 52 15 13 26.000%

## 문제

Fibonacci words are defined similarly to Fibonacci numbers:

FIB1 = b, FIB2 = a, FIBk+2 = FIBk+1 ⊕ FIBk for k ≥ 1,

where ⊕ denotes operation of connecting words (concatenation).

Hence we have: FIB3 = ab, FIB4 = aba, FIB5 = abaab, FIB6 = abaababa.

Write a program that:

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

## 입력

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

## 출력

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 FIBn.

## 예제 입력 1

aba
6


## 예제 출력 1

3