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.

Subtask 1 (10 points): \(1 \le n \le 15\)

Subtask 2 (30 points): \(0 \le k \le 3\)

Subtask 3 (70 points): No additional constraints.

The first line contains integers \(n\) (\(1 \le n \le 2000\)) and \(k\) (\(0 \le k \le 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 \(10^{9} + 7\).

생성자가 기록되지 않았습니다.

출처 COCI 2020/2021 Contest 6