← 返回题目列表

Codeforces · 1393/E1

E1. 暮光与上古卷轴(简单版)

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

这是问题 E 的更简单版本,约束更小。

暮光闪闪收到了来自塞拉斯蒂娅公主的新任务。这次她要求破译包含小马起源重要知识的古卷。

为了隐藏重要信息,不让邪恶之眼看到,小马长老们在卷轴上施展了咒语。该咒语在任何位置都将一个字母精确地添加到它所施展的每个单词上。为了让通向知识的道路更加纠结,长老们选择了卷轴上的一些文字,并对它们施展了咒语。

暮光闪闪知道长老们崇尚万物的秩序,因此卷轴原卷中的单词按照字典顺序非降序排列。她被要求从卷轴的一些单词中删除一个字母(以解除咒语)以获得原始卷轴的某个版本。

不幸的是,恢复远古卷轴的方法可能不止一种。为了不让暮光溜走重要的知识,你必须浏览原始卷轴的所有变体并找到所需的一个。为了估计暮光可能花在这项工作上的最长时间,她需要知道她必须检查的变体数量。她要求你找到那个号码!由于该数字可能非常大,Twilight 要求您对 $$$10^9+7$$$ 求模。

塞拉斯蒂娅公主可能发送了错误的卷轴,因此答案可能不存在。

当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:

- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中有一个字母比 $$$b$$$ 中的对应字母更早出现。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 1000$$$):卷轴中的字数。

接下来的 $$$n$$$ 行的第 $$$i$$$ 行包含一个由小写英文字母组成的字符串:卷轴中的第 $$$i$$$ 个单词。每个单词的长度大于或等于$$$1$$$。单词长度总和不超过$$$20000$$$。

输出

打印一个整数:从滚动模 $$$10^9+7$$$ 中获取原始版本的方法数。

示例

输入 #1

3
abcd
zaza
ataka

输出 #1

4

输入 #2

4
dfs
bfs
sms
mms

输出 #2

8

输入 #3

3
abc
bcd
a

输出 #3

0

输入#4

6
lapochka
kartyshka
bigbabytape
morgenshtern
ssshhhiiittt
queen

输出#4

2028

注意

请注意,长老们可能写了一个空词(但他们肯定对它施了咒语,所以它现在的长度为$$$1$$$)。