Олимпиадный тренинг

Задача . G1. Строки Фибоначчи


Задача

Темы: Строки *2400

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

  • 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). Ответы для строк выводите в том порядке, в котором строки записаны во входных данных.


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

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет