루미 알고리즘

#1619플래티넘Danish

PO 2025 온라인 예선코딩출제 Theodor Beskow영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Boschua is moving to Lund to study at LTH. You've learned that Lund is in Skåne, and now you're worried that Boschua might start sounding Danish.

To prevent this, you want to show Boschua how many words don't sound Danish at all. According to you, a word sounds Danish if it contains at least one word from the Danish dictionary. Unfortunately, you don't have access to the official Danish dictionary, but the old dictionary you found in the basement will have to suffice.

For example, suppose the dictionary only contains the word knallert. Then you consider the word husknallertrumma to sound Danish because it contains the word knallert. On the other hand, you consider the word knallerunt to not sound Danish because it does not contain knallert.

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 1: The word husknallertrumma sounds Danish.

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 1: The word knallerunt does not sound Danish.

You quickly realize there are too many words that don't sound Danish to list them all. Thus, you decide it's sufficient to count the number of words that don't sound Danish and share that with Boschua. Even this turns out to be difficult since there are so many words that don't sound Danish.

Finally, you settle for counting the number of words that consist of only lowercase English letters a-z, have exactly N letters, and don't sound Danish. A word sounds Danish if it contains at least one word from the dictionary as a substring.

Input

The first line of input contains the integers N (1 ≤ N ≤ 100) and M (0 ≤ M ≤ 150), the length of the words being considered and the number of words in the dictionary.

The following M lines each contain a word from the dictionary. All these words have a length of at most N and consist of the letters a-z. All words in the dictionary are unique.

Output

Print the number of words of length N that don't sound too Danish. Since this number can be very large, output it modulo (https://en.wikipedia.org/wiki/Modulo) 10^9+7.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
110M = 0
213N ≤ 3, M ≤ 10
323M = 1
432N, M ≤ 50
522No additional constraints.

Explanation of Samples

In the first sample, there are 26^3 different words. Since the Danish dictionary is empty in this case, none of them are forbidden.

예제

예제 1

입력
3 0
출력
17576

예제 2

입력
2 2
a
po
출력
624

예제 3

입력
5 5
java
py
js
rust
apl
출력
11738952

출처 표기

출처: Programmeringsolympiaden 2025년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.