题目描述

译自 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$\}$。

5 2
trava
vatra
vrata
leo
ole

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$ 内的字符串仅有小写字母组成且互不相同。