|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||128 MB||63||16||15||28.846%|
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:
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.