문자열 성적

바이트랜드 주립대학교에서 성적은 길이가 같은 문자열이다. 문자열 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에 대해, x1 = y1, x2 = y2, ..., xi - 1 = yi - 1, xi < yi를 만족하는 i가 존재하면 x가 y보다 사전순으로 작다.

답이 매우 클 수 있으므로, 답을 109 + 7로 나눈 나머지를 구해야 한다.

첫 번째 줄에 문자열 a가, 두 번째 줄에 문자열 b가 주어진다. 문자열 a, b는 영문 소문자로 구성된다. 두 문자열의 길이는 같으며 106을 초과하지 않는다.

a가 b보다 사전순으로 작음이 보장된다.

문제의 조건을 만족하는 서로 다른 문자열의 수를 109 + 7로 나눈 나머지를 나타내는 정수 하나를 출력한다.

첫 번째 예제에서 문자열 abc로부터 acb, bac, bca, cab, cba를 얻을 수 있으며, 이들은 모두 abc보다 크지만 ddd보다 작다. 따라서 답은 5이다.

두 번째 예제에서는 abcdef로부터 얻을 수 있는 모든 문자열이 abcdeg보다 크다. 따라서 답은 0이다.