在 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。