감독

학생들이 잠을 좋아한다는 사실은 이제 잘 알려져 있다. 파트리크는 이 분야의 기록 보유자다. 그는 밥을 먹어야 하거나 FIFA 20을 하고 싶을 때만 깨어난다. 그래서 그의 꿈은 보통 축구를 중심으로 펼쳐진다. 지난 꿈에서 그는 자신이 가장 좋아하는 팀인 GNK 디나모 자그레브의 축구 감독이 되어 있었다.

그의 일은 다음 시즌에 파란 유니폼을 입을 선수 N명을 선발하는 것이지만, 이사회가 몇 가지 까다로운 요구를 내걸었다. 요구 사항은 다음과 같다.

• 모든 선수의 성은 길이가 서로 달라야 한다.
• 어떤 선수의 성은, 그보다 성이 긴 모든 선수의 성에 연속 부분 문자열로 나타나야 한다.

일을 쉽게 하기 위해 파트리크는 후보 선수들을 N개의 바구니로 나누었고, i번째 바구니에는 성이 정확히 i글자인 선수가 들어 있다. 각 바구니에는 선수가 정확히 K명씩 있다. 파트리크는 주어진 요구 사항을 만족하면서 자신의 팀을 위해 선수를 선택하는 서로 다른 방법의 수가 몇 가지인지 (modulo 10^9 + 7) 알고 싶어 한다.

첫째 줄에 두 정수 N (1 ≤ N ≤ 50)과 K (1 ≤ K ≤ 1 500)가 주어진다.

다음 N개 줄에는 각각 K개의 성이 주어지며, 서로 같아도 된다. 이 중 i번째 줄에 있는 선수들의 성은 영어 알파벳 소문자 정확히 i글자로 이루어져 있다.

한 줄에 문제 설명의 정답을 출력한다.