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