Description

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$.

Input Format

The first line contains two integers $n$ and $k$.

The next $n$ lines each contain a string, representing a word.

Output Format

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

3 1
ovo
ono
voo

2

5 2
trava
vatra
vrata
leo
ole

3

6 3
mali
lima
imal
je
sve
ej

6

Hint

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.

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 CONTEST #6 T3 Anagramistica。

Translated by ChatGPT 5