시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 4 3 2 66.667%

문제

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