题目描述

Biljana 喜欢出字谜游戏。

如果一个单词可以由另一个单词交换字母顺序得到，则称它们是「相似」的。

现在，她有 $n$ 个单词。她希望选出一些单词，使得其中恰好有 $k$ 对单词是「相似」的。请你帮她计算可行的方案数，对 $10^9 + 7$ 取模。

输入格式

第一行两个整数 $n$，$k$。

接下来 $n$ 行，每行一个字符串，表示一个单词。

输出格式

一行一个整数，表示可行的方案数，对 $10^9 + 7$ 取模。

3 1
ovo
ono
voo

2

5 2
trava
vatra
vrata
leo
ole

3

6 3
mali
lima
imal
je
sve
ej

6

提示

样例 1 解释

恰含有一对「相似」的单词的方案为 ovo, ono, voo 和 ovo, voo。

数据规模与约定

本题采用捆绑测试。

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^3$，$0 \le k \le 2 \times 10^3$，单词的长度不超过 $10$ 且仅含小写字母。

说明

本题分值按 COCI 原题设置，满分 $110$。

题目译自 COCI2020-2021 CONTEST #6 T3 Anagramistica。