#4008. [ABC 246] F. typewriter

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Reqwey

题目描述

我们有一个 行的打字机,第 行的键盘只可以打出字符串 中的所有字符。

我们要用这个打字机按如下的步骤打出一个字符串:

  1. 选一个整数
  2. 用从上往下数第 行的键盘打出一个长为 的字符串。

你需要输出可以打出的不同的字符串的数量 的结果。

输入格式

  • 第一行包含两个整数 ,以一个空格隔开。
  • 行中,第 行为一个字符串

输出格式

输出答案,对 取模。

样例

样例输入 1

2 2
ab
ac

样例输出 1

7

样例解释 1

我们可以打出 个不同的字符串,aaabacbabbcacc

样例输入 2

4 3
abcdefg
hijklmnop
qrstuv
wxyz

样例输出 2

1352

样例输入 3

5 1000000000
abc
acde
cefg
abcfh
dghi

样例输出 3

346462871

数据范围与提示

  • 都是整数。
  • 中的所有字符都不相同,且都是小写英文字母。