Числа Фибоначчи

Последовательность слов Фибоначчи из битовых строк определяется следующим образом:

Здесь символ + обозначает конкатенацию строк. Первые несколько элементов последовательности:

Дан битовый шаблон p и число n. Сколько раз шаблон p встречается в строке F(n)?

Входные данные

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

Выходные данные

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

Примеры