暮光闪闪与古代卷轴（加强版）

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

一份古代卷轴包含 $n$ 个单词。长老可能对其中某些单词施加魔法：在单词的任意位置恰好插入一个字母。原卷轴中的单词按字典序非递减排列。

现在需要从每个单词中选择“不删除”或“删除恰好一个位置的字母”，使得到的单词序列按字典序非递减。不同的删除位置视为不同恢复方案；即使删除相同连续字母得到的字符串相同，这些方案仍分别计数。

求恢复方案数，对 $10^9+7$ 取模。如果不存在方案，输出 $0$。

字符串 $a$ 的字典序小于字符串 $b$，当且仅当：$a$ 是 $b$ 的真前缀；或二者第一个不同位置上 $a$ 的字母更小。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行一个只含小写英文字母的非空字符串，表示当前卷轴中的一个单词。

输出格式

输出恢复方案数对 $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\le n\le10^5$，每个单词长度至少为 $1$，所有单词长度之和不超过 $10^6$。

每个测试点独立计分。