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
Input Specification
The first line contains integers
Each of the following
Output Specification
Output the number of described subsets modulo
Constraints
Subtask | Points | Constraints |
---|---|---|
1 | 10 | |
2 | 30 | |
3 | 70 | No additional constraints. |
Sample Input 1
3 1
ovo
ono
voo
Sample Output 1
2
Explanation for Sample Output 1
Subsets with exactly one similar pair are {ovo
, ono
, voo
} and {ovo
, voo
}.
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
Comments