G2. Строки Фибоначчи
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Строки Фибоначчи определяются следующим образом:

  • f1 = «a»
  • f2 = «b»
  • fn = fn - 1 fn - 2, n > 2

Таким образом, первые пять строк Фибоначчи: «a», «b», «ba», «bab», «babba».

Вам дана строка Фибоначчи и m строк si. Для каждой строки si найдите, сколько раз она встречается в данной строке Фибоначчи в качестве подстроки.

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

В первой строке записано два целых числа через пробел k и m — номер строки Фибоначчи и количество запросов, соответственно.

В следующих m строках записаны строки si, соответствующие запросам. Гарантируется, что строки si непусты и состоят только из символов «a» и «b».

Ограничения на входные данные для получения 30 баллов:

  • 1 ≤ k ≤ 3000
  • 1 ≤ m ≤ 3000
  • Суммарная длина строк si не превосходит 3000

Ограничения на входные данные для получения 100 баллов:

  • 1 ≤ k ≤ 1018
  • 1 ≤ m ≤ 104
  • Суммарная длина строк si не превосходит 105

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

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

Для каждой строки si выведите, сколько раз она встречается в заданной строке Фибоначчи в качестве подстроки. Так как числа могут оказаться достаточно большими, выводите их остатки от деления на 1000000007 (109 + 7). Ответы для строк выводите в том порядке, в котором строки записаны во входных данных.

Примеры
Входные данные
6 5
a
b
ab
ba
aba
Выходные данные
3
5
3
3
1