One day Polycarpus got hold of two non-empty strings s and t, consisting of lowercase Latin letters. Polycarpus is quite good with strings, so he immediately wondered, how many different pairs of "x y" are there, such that x is a substring of string s, y is a subsequence of string t, and the content of x and y is the same. Two pairs are considered different, if they contain different substrings of string s or different subsequences of string t. Read the whole statement to understand the definition of different substrings and subsequences.

The length of string s is the number of characters in it. If we denote the length of the string s as |s|, we can write the string as s = s1s2... s|s|.

A substring of s is a non-empty string x = s[a... b] = sasa + 1... sb (1 ≤ a ≤ b ≤ |s|). For example, "code" and "force" are substrings or "codeforces", while "coders" is not. Two substrings s[a... b] and s[c... d] are considered to be different if a ≠ c or b ≠ d. For example, if s="codeforces", s[2...2] and s[6...6] are different, though their content is the same.

A subsequence of s is a non-empty string y = s[p1p2... p|y|] = sp1sp2... sp|y| (1 ≤ p1 < p2 < ... < p|y| ≤ |s|). For example, "coders" is a subsequence of "codeforces". Two subsequences u = s[p1p2... p|u|] and v = s[q1q2... q|v|] are considered different if the sequences p and q are different.

Input

The input consists of two lines. The first of them contains s (1 ≤ |s| ≤ 5000), and the second one contains t (1 ≤ |t| ≤ 5000). Both strings consist of lowercase Latin letters.

Output

Print a single number — the number of different pairs "x y" such that x is a substring of string s, y is a subsequence of string t, and the content of x and y is the same. As the answer can be rather large, print it modulo 1000000007 (109 + 7).

Examples

Input

aa
aa


Output

5


Input

codeforces
forceofcode


Output

60

Note

Let's write down all pairs "x y" that form the answer in the first sample: "s[1...1] t[1]", "s[2...2] t[1]", "s[1...1] t[2]","s[2...2] t[2]", "s[1...2] t[1 2]".
#include <bits/stdc++.h>
using namespace std;
template <class Iter, class T>
Iter closest_value(Iter begin, Iter end, T value) {
  Iter result = upper_bound(begin, end, value);
  if (result != begin) {
    Iter lower_result = result;
    --lower_result;
    if (result == end || ((value - *lower_result) < (*result - value))) {
      result = lower_result;
    }
  }
  return result;
}
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
set<long long int> s;
void sieve() {
  bool prime[100005 + 5];
  memset(prime, true, sizeof(prime));
  for (long long int p = 2; p * p <= 100005; p++) {
    if (prime[p] == true) {
      for (long long int i = p * 2; i <= 100005; i += p) prime[i] = false;
    }
  }
  for (int p = 2; p <= 100005; p++)
    if (prime[p]) s.insert(p);
}
long long int gcd(long long int a, long long int b) {
  while (a > 0 && b > 0) {
    if (a > b) {
      a %= b;
    } else {
      b %= a;
    }
  }
  return a + b;
}
long long int lcm(long long int a, long long int b) {
  return a / gcd(a, b) * b;
}
bool isPerfectSquare(long long int n) {
  if (n < 0) return false;
  long long int tst = (long long int)(sqrt(n) + 0.5);
  return tst * tst == n;
}
bool ft(long long int a, long long int b, long long int c) {
  return ((a + b) > c && (b + c) > a && (a + c) > b);
}
int dp[5005][5005];
int f[5006][5006];
int main() {
  string a, b;
  cin >> a >> b;
  memset(dp, 0, sizeof(dp));
  for (long long int i = 1; i <= a.length(); i++) {
    for (long long int j = 1; j <= b.length(); j++) {
      dp[i][j] = dp[i][j - 1];
      if (a[i - 1] == b[j - 1]) {
        dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] + 1) % 1000000007;
      }
    }
  }
  long long int ans = 0;
  for (long long int i = 1; i <= a.length(); i++)
    ans = (ans + dp[i][b.length()]) % 1000000007;
  cout << ans << endl;
  return 0;
}
