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.PrintWriter;
import java.util.Scanner;


public class C {

    /**
     * @param args
     */
    public static void main(String[] args) {
        Subs subs = new Subs();
        subs.sol();
        subs.print();
    }

}

class Subs {
    
    Subs() {
        Scanner scr = new Scanner(System.in);
        String fs = scr.nextLine();
        String ft = scr.nextLine();
        s = fs.toCharArray();
        t = ft.toCharArray();
        scr.close();
    }
    
    void sol() {
        //long[][] dp = new long[s.length + 1][t.length + 1]; - memory limit
        long[] pred = new long[s.length+1];
        long[] curr = new long[s.length+1];

        ans = 0;
        long save;
        for (int j = 1; j <= t.length; j++){
            save = pred[0];
            for (int i = 1; i <= s.length; i++){
        
                /* de facto, but it's too slowly
                if (s[i-1] == t[j-1]) {
                    for (int k = 0; k < j; k++){
                        dp[i][j] = (dp[i][j] + dp[i-1][k]) % M;
                    }
                    dp[i][j] += 1;
                    ans = (ans + dp[i][j]) % M;
                */
                
                //dp[i][j] = dp[i][j-1];                
                curr[i] = pred[i];
                if (s[i-1] == t[j-1]){
                    //dp[i][j] = (dp[i][j] + dp[i-1][j-1] + 1) % M;
                    curr[i] = (curr[i] + save + 1) % M;
                }
                save = pred[i];
                pred[i] = curr[i];
            }
        }
        for (int i = 1; i <= s.length; i++){
            //ans = (ans + dp[i][t.length]) % M;
            ans = (ans + curr[i]) % M;
        }
    }
    
    void print() {
        PrintWriter pw = new PrintWriter(System.out);
        pw.println(ans);
        pw.flush();
        pw.close();
    }

    long ans;
    char[] s;
    char[] t;
    static final int M = 1000000007;
}