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

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

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

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

입력 형식

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

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

출력 형식

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

예제 입력

3 4
ac
cd
bd

예제 출력

4