← 返回题目列表

Codeforces · 895/D

D. 字符串标记

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

在 Byteland 州立大学,标记是相同长度的字符串。如果字符串 y 按字典顺序小于 x,则标记 x 被认为比 y 更好。

最近,BSU 进行了一项重要的测试工作,Vasya 获得了 a 分。老师很难记住每个学生的准确分数,但他知道分数b,因此每个学生得到的分数都严格小于b。

Vasya 对自己的分数不满意,因此他决定改进它。他可以根据需要多次交换与他的标记相对应的字符串中的字符。现在他只想知道提高成绩的不同方法的数量,这样他的老师就不会注意到可疑的事情。

更正式地说:给你两个长度相同的字符串 a, b,你需要计算出不同字符串 c 的数量,这样:

1) a可以通过交换一些字符得到c,即c是a的排列。

2) 字符串 a 按字典顺序小于 c。

3) 字符串 c 按字典顺序小于 b。

对于长度相同的两个字符串 x 和 y,如果存在这样的 i,即 x1 = y1, x2 = y2, ..., xi - 1 = yi - 1, xi < yi,则 x 按字典顺序小于 y。

由于答案可能非常大,因此您需要找到对 109 + 7 求模的答案。

输入

第一行包含字符串 a,第二行包含字符串 b。字符串a、b由小写英文字母组成。它们的长度相等且不超过 106。

保证a 按字典顺序小于b。

输出

打印一个整数——满足问题条件的不同字符串的数量模 109 + 7。

示例

输入 #1

abc
ddd

输出 #1

5

输入 #2

abcdef
abcdeg

输出 #2

0

输入 #3

abacaba
ubuduba

输出 #3

64

注意

在第一个样本中,从字符串 abc 可以得到字符串 acb、bac、bca、cab、cba,它们都大于 abc,但小于 ddd。所以答案是5。

在第二个示例中,从 abcdef 获得的任何字符串都大于 abcdeg。所以答案是0。