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.util.*;
import java.io.*;

public class cf163a {
    static char[] s, t;
    static int mod = 7+(int)1e9;
    static int[][] memo;
    public static void main(String[] args) throws Exception {
        FastScanner in = new FastScanner(System.in);
        s = in.next().trim().toCharArray();
        t = in.next().trim().toCharArray();
        memo = new int[s.length+1][t.length+1];
        for(int[] x : memo) Arrays.fill(x,-1);
        long ret = 0;
        int[] first = new int[26];
        Arrays.fill(first,-1);
        for(int i=t.length-1; i>=0; i--)
            first[t[i]-'a'] = i;
        for(int i=0; i<s.length; i++)
            if(first[s[i]-'a'] != -1)
                ret = (ret+go(i,first[s[i]-'a']))%mod;
        System.out.println(ret);
    }
    static int go(int sPos, int tPos) {
        if(sPos == s.length || tPos == t.length) return 0;
        if(memo[sPos][tPos] != -1) return memo[sPos][tPos];
        int ret = go(sPos,tPos+1);
        if(s[sPos]==t[tPos]) ret = (ret+1+go(sPos+1,tPos+1))%mod;
        return memo[sPos][tPos] = ret;
    }
    
    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        
        FastScanner(InputStream in) throws Exception{
            br = new BufferedReader(new InputStreamReader(in));
            st = new StringTokenizer(br.readLine().trim());
        }
        public int numTokens() throws Exception {
            if(!st.hasMoreTokens()) {
                st = new StringTokenizer(br.readLine().trim());
                return numTokens();
            }
            return st.countTokens();
        }
        public String next() throws Exception {
            if(!st.hasMoreTokens()) {
                st = new StringTokenizer(br.readLine().trim());
                return next();
            }
            return st.nextToken();
        }
        public double nextDouble() throws Exception {
            return Double.parseDouble(next());
        }
        public long nextLong() throws Exception {
            return Long.parseLong(next());
        }
        public int nextInt() throws Exception {
            return Integer.parseInt(next());
        }
    }
}

/*

aa
aa

codeforces
forceofcode

*/