34695번 - 이름 짓기

문제

오늘도 평화로운 대곽 나라에서는 다음과 같은 규칙으로 이름을 짓는다.

• 이름은 알파벳 소문자로만 이루어진다.
• 이름의 글자 수는 2ドル$자 이상 $N$자 이하여야 한다.
• 이름의 모든 연속된 2ドル$자는 허용된 조합이어야 한다.

예를 들어, 'ac', 'bd', 'cd'가 허용된 조합이라고 하자. 'acd'는 'ac' 와 'cd'가 모두 허용된 조합 이므로 사용 가능한 이름이다. 하지만 'abd'는 'ab'가 허용된 조합이 아니기 때문에 사용할 수 없다.

허용된 조합이 주어질 때, 규칙을 준수하면서 만들 수 있는 이름의 총 개수를 구해 보자.

입력

첫째 줄에 허용된 조합의 수 $K,ドル 이름의 최대 글자 수 $N$이 공백으로 구분되어 주어진다. $(1 \leq K \leq 676$; 2ドル \leq N \leq 100,000円)$

다음 $K$개 줄에 걸쳐 각각 허용된 조합을 나타내는 문자열 $s$가 주어진다. $s$는 알파벳 소문자 2ドル$자로 이루어져 있으며, $K$개의 문자열은 서로 다르다.

출력

만들 수 있는 이름의 총 개수를 10ドル^9 + 7$로 나눈 나머지를 출력한다.

제한

노트