A1395. [COCI-2020-2021-contest6]#2 Anagramistica
编程题
普及/提高-
知识点
题目描述
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.
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.
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.
7.
输入输出样例
输入 #1
3 1 ovo ono voo
输出 #1
3
输入 #2
5 2 trava vatra vrata leo ole
输出 #2
3
说明/提示
Subtask Points Constraints
1 10 1 ≤ n ≤ 15
2 30 0 ≤ k ≤ 3
3 70 No additional constraints.
Clarification of the first example:
Subsets with exactly one similar pair are {ovo, ono, voo} and {ovo, voo}.
1 10 1 ≤ n ≤ 15
2 30 0 ≤ k ≤ 3
3 70 No additional constraints.
Clarification of the first example:
Subsets with exactly one similar pair are {ovo, ono, voo} and {ovo, voo}.