CF895D String Mark

在 Byteland 州立大学，成绩是等长的字符串。如果字符串 $y$ 按字典序小于 $x$，则成绩 $x$ 被认为比 $y$ 好。 最近在 BSU 进行了一次重要的测试，Vasya 得到了成绩 $a$。教师很难记住每个学生的确切成绩，但他知道某个成绩 $b$，所有学生的成绩都严格小于 $b$。 Vasya 对自己的成绩不满意，他决定提升成绩。他可以任意次数交换自己成绩字符串中的字符。现在他想知道，有多少种不同的方法可以提升自己的成绩，同时不让老师察觉到任何异常。 更正式地说：给定两个等长字符串 $a$ 和 $b$，需要计算有多少不同的字符串 $c$ 满足以下条件： 1）$c$ 可以通过交换 $a$ 中的某些字符获得，换句话说，$c$ 是 $a$ 的一个排列。 2）字符串 $a$ 按字典序小于 $c$。 3）字符串 $c$ 按字典序小于 $b$。 对于两个等长的字符串 $x$ 和 $y$，如果存在某个下标 $i$，使得 $x_1 = y_1, x_2 = y_2, ..., x_{i-1} = y_{i-1}, x_i < y_i$，则 $x$ 按字典序小于 $y$。 由于答案可能非常大，结果需要对 $10^9+7$ 取模。

第一行输入字符串 $a$，第二行输入字符串 $b$。字符串 $a, b$ 由小写英文字母组成，长度相等且不超过 $10^6$。 保证 $a$ 按字典序小于 $b$。

输出一个整数，表示满足题意的不同字符串数量，对 $10^9+7$ 取模。

在第一个样例中，可以由字符串 $abc$ 得到字符串 $acb, bac, bca, cab, cba$，它们都比 $abc$ 大且比 $ddd$ 小，所以答案是 $5$。 在第二个样例中，由 $abcdef$ 得到的任意字符串都比 $abcdeg$ 大。所以答案是 $0$。 由 ChatGPT 5 翻译