[AdditionalFile3484.zip](file://AdditionalFile3484.zip?type=additional_file)

#3484. 「COCI 2021.3」Anagramistica

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

译自 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

满足条件的子集有 $\{$ovo$,$ono$,$voo$\}$ 和 $\{$ovo$,$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$ 内的字符串仅有小写字母组成且互不相同。