String Mark

题意翻译

给定两个字符串s1,s2，保证字典序s1<s2。求一个字符串s3,使得s1<s3<s2，并且s3是s1的一个排列。求满足条件的s3数量。 感谢 @ObsdianGungnir 提供的翻译。

题目描述

At the Byteland State University marks are strings of the same length. Mark $ x $ is considered better than $ y $ if string $ y $ is lexicographically smaller than $ x $ . Recently at the BSU was an important test work on which Vasya recived the mark $ a $ . It is very hard for the teacher to remember the exact mark of every student, but he knows the mark $ b $ , such that every student recieved mark strictly smaller than $ b $ . Vasya isn't satisfied with his mark so he decided to improve it. He can swap characters in the string corresponding to his mark as many times as he like. Now he want to know only the number of different ways to improve his mark so that his teacher didn't notice something suspicious. More formally: you are given two strings $ a $ , $ b $ of the same length and you need to figure out the number of different strings $ c $ such that: 1\) $ c $ can be obtained from $ a $ by swapping some characters, in other words $ c $ is a permutation of $ a $ . 2\) String $ a $ is lexicographically smaller than $ c $ . 3\) String $ c $ is lexicographically smaller than $ b $ . For two strings $ x $ and $ y $ of the same length it is true that $ x $ is lexicographically smaller than $ y $ if there exists such $ i $ , that $ x_{1}=y_{1},x_{2}=y_{2},...,x_{i-1}=y_{i-1},x_{i}<y_{i} $ . Since the answer can be very large, you need to find answer modulo $ 10^{9}+7 $ .

输入输出格式

输入格式

First line contains string $ a $ , second line contains string $ b $ . Strings $ a,b $ consist of lowercase English letters. Their lengths are equal and don't exceed $ 10^{6} $ . It is guaranteed that $ a $ is lexicographically smaller than $ b $ .

输出格式

Print one integer — the number of different strings satisfying the condition of the problem modulo $ 10^{9}+7 $ .

输入输出样例

输入样例 #1

abc
ddd

输出样例 #1

5

输入样例 #2

abcdef
abcdeg

输出样例 #2

0

输入样例 #3

abacaba
ubuduba

输出样例 #3

64

说明

In first sample from string $ abc $ can be obtained strings $ acb,bac,bca,cab,cba $ , all of them are larger than $ abc $ , but smaller than $ ddd $ . So the answer is $ 5 $ . In second sample any string obtained from $ abcdef $ is larger than $ abcdeg $ . So the answer is $ 0 $ .