CF1393E2.Twilight and Ancient Scroll (harder version)

This is a harder version of the problem E with larger constraints.

Twilight Sparkle has received a new task from Princess Celestia. This time she asked to decipher the ancient scroll containing important knowledge of pony origin.

To hide the crucial information from evil eyes, pony elders cast a spell on the scroll. That spell adds exactly one letter in any place to each word it is cast on. To make the path to the knowledge more tangled elders chose some of words in the scroll and cast a spell on them.

Twilight Sparkle knows that the elders admired the order in all things so the scroll original scroll contained words in lexicographically non-decreasing order. She is asked to delete one letter from some of the words of the scroll (to undo the spell) to get some version of the original scroll.

Unfortunately, there may be more than one way to recover the ancient scroll. To not let the important knowledge slip by Twilight has to look through all variants of the original scroll and find the required one. To estimate the maximum time Twilight may spend on the work she needs to know the number of variants she has to look through. She asks you to find that number! Since that number can be very big, Twilight asks you to find it modulo $10^9+7$.

It may occur that princess Celestia has sent a wrong scroll so the answer may not exist.

A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds:

• $a$ is a prefix of $b$, but $a \ne b$;
• in the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$.

这是问题 E 的一个难度更高的版本，约束条件更大。

暮光闪闪从宇宙公主塞拉斯蒂娅那里接到了一项新任务。这一次，她被要求破译一份记载着小马起源重要知识的远古卷轴。

为了防止关键信息落入邪恶之眼，小马长老们在卷轴上施加了一道咒语。该咒语会对所作用的每个单词恰好添加一个字母（可插入到任意位置）。为了让通往知识的道路更加错综复杂，长老们选择卷轴中部分单词施加了该咒语。

暮光闪闪知道，长老们崇尚万物有序，因此原始卷轴中的单词是按字典序非递减顺序排列的。她需要对卷轴中某些单词删除一个字母（即逆转咒语），从而恢复出某种可能的原始卷轴。

不幸的是，恢复远古卷轴的方式可能不止一种。为避免重要知识被遗漏，暮光闪闪必须逐一检查所有可能的原始卷轴版本，并从中找出所需的那个。为了估算暮光闪闪完成这项工作所需的最长时间，她需要知道待检查的方案总数。请你帮她计算这个数目！由于该数目可能非常大，请你输出其对 $10^9+7$ 取模的结果。

也有可能宇宙公主塞拉斯蒂娅寄来了一份错误的卷轴，此时答案可能不存在。

字符串 $a$ 字典序小于字符串 $b$，当且仅当满足以下条件之一：

• $a$ 是 $b$ 的真前缀（即 $a$ 是 $b$ 的前缀，但 $a \ne b$）；
• 在 $a$ 与 $b$ 首次出现不同字符的位置上，$a$ 中该位置的字母在字母表中早于 $b$ 中对应位置的字母。

The first line contains a single integer $n$ ($1 \le n \le 10^5$): the number of words in the scroll.

The $i$-th of the next $n$ lines contains a string consisting of lowercase English letters: the $i$-th word in the scroll. The length of each word is at least one. The sum of lengths of words does not exceed $10^6$.

第一行包含一个整数 $n$（$1 \le n \le 10^5$）：卷轴中单词的数量。

接下来的 $n$ 行中，第 $i$ 行包含一个由小写英文字母组成的字符串：卷轴中的第 $i$ 个单词。每个单词的长度至少为 $1$，所有单词长度之和不超过 $10^6$。

Print one integer: the number of ways to get a version of the original from the scroll modulo $10^9+7$.

输出一个整数：从卷轴中得到原始版本的方案数对 $10^9+7$ 取模的结果。

Notice that the elders could have written an empty word (but they surely cast a spell on it so it holds a length $1$ now).

注意，长老们可能写了一个空单词（但他们肯定对其施加了咒语，因此它现在的长度为 $1$）。