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 x1 = y1, x2 = y2, ..., xi - 1 = yi - 1, xi < yi.

Since the answer can be very large, you need to find answer modulo 109 + 7.

Input

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 106.

It is guaranteed that a is lexicographically smaller than b.

Output

Print one integer — the number of different strings satisfying the condition of the problem modulo 109 + 7.

Examples

Input

abc
ddd


Output

5


Input

abcdef
abcdeg


Output

0


Input

abacaba
ubuduba


Output

64

Note

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.
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const long long N = 1e6 + 11;
long long num[28];
long long num2[28];
char s[N], lm[N];
long long len;
long long fac[N];
long long inv[N];
long long finv[N];
long long powmod(long long a, long long b, long long mod) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return ans;
}
void initt() {
  fac[0] = inv[0] = finv[0] = 1;
  for (int i = 1; i < N; i++) {
    fac[i] = fac[i - 1] * i % mod;
  }
  for (int i = 1; i < N; i++) {
    finv[i] = powmod(fac[i], mod - 2, mod);
  }
}
long long solve(long long *num, char *s) {
  long long ans = 0, tt = 1;
  for (int i = 0; i < len; i++) {
    long long t = 0;
    for (int j = 0; j < s[i]; j++) {
      t += num[j];
    }
    ans = (ans + tt * t % mod * fac[len - i - 1] % mod) % mod;
    if (num[s[i]] == 0) break;
    tt = tt * num[s[i]] % mod;
    if (num[s[i]] > 0) num[s[i]]--;
  }
  return ans;
}
int main() {
  initt();
  scanf("%s", s);
  scanf("%s", lm);
  len = strlen(s);
  for (int i = 0; i < len; i++) {
    s[i] -= 'a';
    num[s[i]]++;
  }
  for (int i = 0; i < len; i++) {
    lm[i] -= 'a';
  }
  if (strcmp(s, lm) == 0) {
    puts("0");
    return 0;
  }
  long long tt = 1;
  for (int i = 0; i < 26; i++) {
    tt = tt * finv[num[i]] % mod;
  }
  for (int i = 0; i < 26; i++) num2[i] = num[i];
  long long ans = solve(num, lm) - solve(num2, s);
  printf("%lld\n", (ans % mod * tt % mod + mod - 1) % mod);
}
