← 返回题目列表

Codeforces · 152/C

C. 袖珍书

中文机器翻译题面 查看原题

有一天,小瓦夏发现了妈妈的口袋书。这本书里有她的 n 个朋友的名字,而且不同寻常的是,每个名字的长度正好是 m 个字母。让我们按照名字的书写顺序从 1 到 n 编号。

由于妈妈不在家,Vasya 决定玩玩名字:他选择了三个整数 i、j、k(1 ≤ i < j ≤ n、1 ≤ k ≤ m),然后他取了名字 i 和 j 并交换了长度为 k 的前缀。例如,如果我们将名称“CBDAD”和“AABRD”交换为长度为 3 的前缀,则结果将是名称“AABAD”和“CBDRD”。

如果允许 Vasya 执行任意数量的所描述的操作,您想知道 Vasya 可以写多少个不同的名字来代替名字 1。当 Vasya 执行每个动作时,他独立于之前的动作选择数字 i、j、k,并且他的选择完全基于他的意志。所查找的数字可能非常大,因此您只能找到对 1000000007 (109 + 7) 求模的数字。

输入

第一输入行包含两个整数 n 和 m (1 ≤ n, m ≤ 100) — 相应地,名称的数量和每个名称的长度。然后n行包含名字,每个名字恰好由m个大写拉丁字母组成。

输出

打印单个数字 — 应用上述程序后,可能出现在皮夹中第 1 位置的不同姓名的数量。打印以 1000000007 为模的数字 (109 + 7)。

示例

输入 #1

2 3
AAB
BAA

输出 #1

4

输入 #2

4 5
ABABA
BCGDG
AAAAA
YABSA

输出 #2

216

注意

在第一个样本中,Vasya 可以在位置号 1 中获得以下名称:“AAB”、“AAA”、“BAA”和“BAB”。