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]".
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public class C {
    static int[][] next;
    static int[][] dp;
    static char[] s, t;

    static int mod = 1000000007;

    static int solve(int sIdx, int tIdx) {
        if (sIdx == s.length || tIdx == t.length)
            return 1;
        if (dp[sIdx][tIdx] != -1)
            return dp[sIdx][tIdx];
        long res = 0;
        if (next[tIdx][s[sIdx] - 'a'] != -1) {
            res = solve(sIdx, next[tIdx][s[sIdx] - 'a']);
            if (sIdx < s.length - 1 && (next[tIdx][s[sIdx + 1] - 'a'] != -1)) {
                res = ((res + 1) % mod + solve(sIdx + 1,
                        next[tIdx][s[sIdx + 1] - 'a']))
                        % mod;
            } else {
                res = (res + 1) % mod;
            }
        } else {
            if (sIdx < s.length - 1 && (next[tIdx][s[sIdx + 1] - 'a'] != -1)) {
                res = ((res + 1) % mod + solve(sIdx + 1,
                        next[tIdx][s[sIdx + 1] - 'a']))
                        % mod;
            } else
                res = (res + 1) % mod;
        }
        return dp[sIdx][tIdx] = (int) (res % mod);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         s = br.readLine().toCharArray();
         t = br.readLine().toCharArray();
//      s = new char[5000];
//      t = new char[5000];
//      for (int i = 0; i < 5000; i++) {
//          s[i] = 'a';
//          t[i] = 'a';
//      }
        next = new int[t.length][26];
        for (int i = 0; i < t.length; i++)
            Arrays.fill(next[i], -1);
        for (int i = 0; i < t.length; i++) {
            for (int j = i + 1; j < t.length; j++) {
                if (next[i][t[j] - 'a'] == -1) {
                    next[i][t[j] - 'a'] = j;
                }
            }
        }
        dp = new int[s.length+1][t.length+1];
        for (int sIdx = s.length; sIdx >= 0; sIdx--) {
            for (int tIdx = t.length; tIdx >= 0; tIdx--) {
                if (sIdx == s.length || tIdx == t.length) {
                    dp[sIdx][tIdx] = 1;
                    continue;
                }
                if (s[sIdx] != t[tIdx]) {
                    dp[sIdx][tIdx] = 0;
                    continue;
                }
                long res = 0;
                if (next[tIdx][s[sIdx] - 'a'] != -1) {
                    res = dp[sIdx][next[tIdx][s[sIdx] - 'a']];
                    if (sIdx < s.length - 1
                            && (next[tIdx][s[sIdx + 1] - 'a'] != -1)) {
                        res = ((res + 1) % mod + dp[sIdx + 1][next[tIdx][s[sIdx + 1] - 'a']])
                                % mod;
                    } else {
                        res = (res + 1) % mod;
                    }
                } else {
                    if (sIdx < s.length - 1
                            && (next[tIdx][s[sIdx + 1] - 'a'] != -1)) {
                        res = ((res + 1) % mod + dp[sIdx + 1][next[tIdx][s[sIdx + 1] - 'a']])
                                % mod;
                    } else
                        res = (res + 1) % mod;
                }
                dp[sIdx][tIdx] = (int) (res % mod);
            }
        }
//      for (int i = 0; i < s.length; i++)
//          Arrays.fill(dp[i], -1);
    
        long res = 0;
        for (int i = 0; i < s.length; i++) {
            for (int j = 0; j < t.length; j++) {
                if (s[i] == t[j]) {
                    res = (res + dp[i][j]) % mod;
                    break;
                }
            }
        }
        System.out.println(res);
    }
}
