시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB101010100.000%

문제

Biljana loves making crosswords. Her favourite type is the so called anagram crossword, where each clue is an anagram of the required solution.

She has a set of n words that she thinks would be good candidates for her next puzzle. We say that two words are similar if one can be obtained from the other by rearranging the letters (i.e. they are anagrams). She wants to select a subset of her words, such that there are exactly k pairs of similar words in that subset. Help Biljana determine the number of such subsets.

입력

The first line contains integers n (1 ≤ n ≤ 2000) and k (0 ≤ k ≤ 2000), the number of words and the required number of similar pairs.

Each of the following n lines contains a word consisting of at most 10 lowercase letters. All words will be distinct.

출력

Output the number of described subsets modulo 109 + 7.

서브태스크

번호배점제한
110

1 ≤ n ≤ 15

230

0 ≤ k ≤ 3

370

No additional constraints.

예제 입력 1

3 1
ovo
ono
voo

예제 출력 1

2

Subsets with exactly one similar pair are {ovo, ono, voo} and {ovo, voo}.

예제 입력 2

5 2
trava
vatra
vrata
leo
ole

예제 출력 2

3

예제 입력 3

6 3
mali
lima
imal
je
sve
ej

예제 출력 3

6

채점 및 기타 정보

  • 예제는 채점하지 않는다.