K==S
시간 제한1초메모리 제한512 MB
길이 N인 26개 문자 문자열 중에서 주어진 Q개의 금지 문자열을 연속 부분 문자열로 포함하지 않는 것의 개수를 10억 7로 나눈 나머지로 구한다.
문제
진보적인 하드 옥타브 록 곡(소위 "포트"(phort))는 특정한 음악 기보법으로 쓰인다. 이 장르의 록은 단 13개의 서로 다른 음높이만을 기반으로 하며, 다른 옥타브의 음들은 시대에 뒤떨어진 음악적 짐으로 취급된다. 각 음은 길거나 짧을 수 있다. 따라서 록에는 정확히 26개의 서로 다른 음이 존재한다.
당신은 친구의 생일을 기념하여 포트 곡을 작곡하고 마을 중앙 광장에서 밴드와 함께 연주하려고 한다. 포트를 작곡할 때 특정한 음악적 프레이즈를 피해야 하는데, 이들은 대형 음반사들의 오랜 연구 결과로 저작권이 강하게 보호되고 있다. 이 프레이즈들은 매우 기억하기 쉽고 귀에 잘 붙어서, 음반사가 자신들의 음반에 사용할 경우 청취자들을 무의식적으로 특정 음악 회사에 묶어둘 수 있는 것으로 밝혀졌다.
곡은 음의 나열이다. 음악적 프레이즈도 음의 나열이며, 그 음들이 곡의 연속된 부분 수열을 이룰 때, 즉 같은 음들이 곡에서 같은 순서로 연달아 나타날 때 그 프레이즈가 곡에 포함되었다고 한다.
다행히 지금까지 특허가 등록된 금지 프레이즈는 몇 개뿐이다. 따라서 자신만의 곡을 작곡하는 데 상대적인 자유가 있다. 특히 당신은 특정 길이의 허용 가능한 곡의 수에 관심이 있다. 허용 가능한 곡은 금지 프레이즈를 포함하지 않는 곡이다. 곡의 길이는 포함된 음의 수와 같다.
입력
첫 번째 줄에 두 정수 N, Q가 주어진다. (1 ≤ N ≤ 109, 1 ≤ Q ≤ 100) N은 곡의 길이이고, Q는 금지된 음악적 프레이즈의 수이다. 다음 Q개의 줄 각각은 하나의 금지 프레이즈를 나타낸다. 금지 프레이즈의 설명은 길이를 나타내는 양의 정수 L로 시작하고, 이어서 L개의 소문자 영어 알파벳으로 이루어진 문자열이 주어진다. 각 문자는 하나의 록 음을 나타내며, 서로 다른 문자는 서로 다른 음을 나타낸다.
모든 금지 프레이즈의 길이의 합은 100을 넘지 않는다.
출력
길이 N인 서로 다른 허용 가능한 곡의 수를 출력한다. 결과는 1 000 000 007로 나눈 나머지를 출력한다.