题目描述

译自 COCI 2020/2021 Contest #6 T3 「Anagramistica」

有一个含 $n$ 个字符串的集合 $S$，求满足下列条件的该集合的子集个数：

恰有 $k$ 对无序字符串 $(T,R)$，将 $T$ 经过打乱后可以获得 $R$。

由于满足条件的子集个数可能很多，所以请输出满足条件的子集个数 $\bmod 10^9+7$ 的值。

---

输入格式

第一行为两个整数 $n,k$。

接下来 $n$ 行，一行一个字符串 $T$，表示 $S$ 包含字符串 $T$。

---

输出格式

仅一行一个整数，表示满足条件的子集个数 $\bmod 10^9+7$ 的值。

---

样例 1

输入

3 1
ovo
ono
voo

输出

2

解释
满足条件的子集有 $\{\text{ovo},\text{ono},\text{voo}\}$ 和 $\{\text{ovo},\text{voo}\}$。

---

样例 2

输入

5 2
trava
vatra
vrata
leo
ole

输出

3

---

样例 3

输入

6 3
mali
lima
imal
je
sve
ej

输出

6

---

数据范围与提示

对于所有子任务，有 $1\le n\le 2\times 10^3$，$0\le k\le 2\times 10^3$，$0 < S$ 内的字符串长度 $\le 10$，$S$ 内的字符串仅有小写字母组成且互不相同。

子任务编号	特殊限制	分值
1	$n\le 15$	$10/110$
2	$k\le 3$	$30/110$
3	无	$70/110$