Мелодии прогрессивного тяжелого октавного рока (так называемые "форты") записываются с использованием определенной нотной записи. Эта особенность рока построена всего на различных высотах нот, остальные высоты (в других октавах) считаются устаревшим музыкальным балластом. Каждая нота может быть как длинной, так и короткой. Следовательно, в роке ровно различных нот.
Вы собираетесь сочинить фортовую мелодию по случаю дня рождения друга и исполнить ее со своим оркестром на главной городской площади. При сочинении форта вам следует избегать определенных музыкальных фраз, которые защищены авторскими правами в результате длительных исследований, спонсируемых крупными звукозаписывающими компаниями. Установлено, что эти фразы легко запоминаются и могут быть использованы для подсознательной привязки слушателей к определенной музыкальной компании, которая будет использовать эти фразы в своей продукции.
Мелодия представляет собой последовательность нот. Музыкальная фраза также является последовательностью нот и считается содержащейся в мелодии, если ее ноты образуют непрерывную последовательность мелодии, то есть одни и те же ноты появляются в мелодии сразу друг за другом в одном и том же порядке.
К счастью, пока запатентовано лишь несколько запрещенных фраз. Таким образом, у Вас есть относительная свобода в сочинении собственных мелодий. В частности, Вас интересует количество приемлемых мелодий определенной длины. Приемлемой мелодией считается любая мелодия, не содержащая запрещенной фразы. Длина мелодии равна количеству содержащихся в ней нот.
В первой строке записаны два целых числа . — длина мелодии, — количество запрещенных музыкальных фраз. Каждая из следующих строк описывает одну запрещенную фразу. Описание запрещенной фразы начинается с положительного целого числа , обозначающего ее длину, за которым следует строка из строчных английских букв. Каждая буква представляет одну ноту рока, разные буквы обозначают разные ноты.
Сумма длин всех запрещенных фраз не превышает .
Выведите количество различных приемлемых мелодий длины . Выведите результат по модулю .