Слова Фібоначчі#3390
Послідовність слів Фібоначчі з бітових рядків визначається наступним чином:
Тут знак + означає конкатенацію рядків. Ось кілька перших елементів:
Вам дано бітовий шаблон та число . Потрібно визначити, скільки разів шаблон зустрічається в ?
Перша строка кожного тестового випадку містить ціле число (0 \le n \le 100). Друга строка містить бітовий шаблон . Шаблон не є порожнім і має довжину не більше символів.
Для кожного тестового випадку виведіть номер випадку, після якого вкажіть кількість появ бітового шаблону в . Появи можуть перекриватися. Кількість появ буде менше 2^{63}.
Приклад 1