Слова Фібоначчі

Послідовність слів Фібоначчі з бітових рядків визначається наступним чином:

Тут знак + означає конкатенацію рядків. Ось кілька перших елементів:

Вам дано бітовий шаблон p та число n. Потрібно визначити, скільки разів шаблон p зустрічається в F(n)?

Вхідні дані

Перша строка кожного тестового випадку містить ціле число n (0 ≤ n ≤ 100). Друга строка містить бітовий шаблон p. Шаблон p не є порожнім і має довжину не більше 100000 символів.

Вихідні дані

Для кожного тестового випадку виведіть номер випадку, після якого вкажіть кількість появ бітового шаблону p в F(n). Появи можуть перекриватися. Кількість появ буде менше 2^63.

Приклади