CF1393E2 Twilight and Ancient Scroll (harder version)

这是 E 题的加强版，数据范围更大。 Twilight Sparkle 收到了 Princess Celestia 的新任务。这次，她被要求破解一份包含小马起源重要知识的古老卷轴。 为了防止关键信息被恶意之人获取，小马长老们对卷轴施加了魔法。这个魔法会在被施加的每个单词的任意位置插入恰好一个字母。为了让获取知识的道路更加曲折，长老们选择了卷轴中的一些单词并对它们施加了魔法。 Twilight Sparkle 知道，长老们崇尚一切事物的秩序，因此原始卷轴中的单词是按字典序非递减排列的。她需要从卷轴中的某些单词中删除一个字母（以解除魔法），从而得到原始卷轴的某个版本。 然而，恢复古老卷轴的方法可能不止一种。为了不让重要知识被遗漏，Twilight 需要遍历所有可能的原始卷轴版本，并找到所需的那个。为了估算她可能花费的最大时间，她需要知道所有可能的原始卷轴版本的数量。请你帮她计算这个数量！由于答案可能非常大，请输出对 $10^9+7$ 取模后的结果。 有可能 Princess Celestia 送错了卷轴，因此答案可能不存在。 如果字符串 $a$ 在字典序上小于字符串 $b$，当且仅当满足以下条件之一： - $a$ 是 $b$ 的前缀，且 $a \ne b$； - 在 $a$ 和 $b$ 第一个不同的位置，$a$ 的字母在字母表中比 $b$ 的对应字母更靠前。

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

输出一个整数，表示可以恢复出原始卷轴的方案数，对 $10^9+7$ 取模。

注意，长老们可能写下了空单词（但他们一定会对其施加魔法，因此现在长度为 $1$）。 由 ChatGPT 4.1 翻译