P7552 [COCI 2020/2021 #6] Anagramistica

Biljana likes making word puzzles. If one word can be obtained from another word by rearranging its letters, then the two words are called “similar”. Now, she has $n$ words. She wants to select some words such that there are exactly $k$ pairs of “similar” words among them. Please help her compute the number of feasible ways, modulo $10^9 + 7$.

The first line contains two integers $n$ and $k$. The next $n$ lines each contain a string, representing a word.

Output one integer on a single line, representing the number of feasible ways, modulo $10^9 + 7$.

#### Explanation for Sample 1 The selections that contain exactly one pair of “similar” words are `ovo, ono, voo` and `ovo, voo`. ------------ #### Constraints **This problem uses bundled testdata**. | Subtask | Score | Constraints | | :----------: | :----------: | :----------: | | $1$ | $10$ | $1 \le n \le 15$ | | $2$ | $30$ | $0 \le k \le 3$ | | $3$ | $70$ | No additional constraints. | For $100\%$ of the testdata, $1 \le n \le 2 \times 10^3$, $0 \le k \le 2 \times 10^3$, the length of each word is at most $10$, and it contains only lowercase letters. ------------ #### Notes **The score settings of this problem follow the original COCI problem, with full score $110$**. **This problem is translated from [COCI2020-2021](https://hsin.hr/coci/archive/2020_2021/) [CONTEST #6](https://hsin.hr/coci/archive/2020_2021/contest6_tasks.pdf) _T3 Anagramistica_**。 Translated by ChatGPT 5