题目描述
Problem Description
Biljana enjoys creating anagram puzzles.
Two words are considered "similar" if one can be obtained by rearranging the letters of the other.
Given \( n \) words, she wants to select some of these words such that there are exactly \( k \) pairs of words that are "similar". Help her calculate the number of feasible schemes, 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 a single integer, representing the number of feasible schemes modulo \( 10^9 + 7 \).
Sample Input and Output
Sample Input #1
3 1
ovo
ono
voo
Sample Output #1
2
Sample Input #2
5 2
trava
vatra
vrata
leo
ole
Sample Output #2
3
Sample Input #3
6 3
mali
lima
imal
je
sve
ej
Sample Output #3
6
Notes
Sample 1 Explanation
The schemes that contain exactly one pair of "similar" words are ovo, ono, voo and ovo, voo.
Data Size and Constraints
This problem is bundled with subtasks.
| Subtask | Points | Constraints |
|---|---|---|
| 1 | 10 | \( 1 \le n \le 15 \) |
| 2 | 30 | \( 0 \le k \le 3 \) |
| 3 | 70 | No additional constraints |
For \( 100\% \) of the data, \( 1 \le n \le 2 \times 10^3 \), \( 0 \le k \le 2 \times 10^3 \), and the length of each word does not exceed 10 and consists only of lowercase letters.
Notes
The points are set according to the original COCI problem, with a maximum of 110 points.
The problem is translated from COCI2020-2021 CONTEST #6 T3 Anagramistica.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分