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]".
//package vk_cup_round2;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Reader;
import java.io.StreamTokenizer;
import java.io.Writer;
/**
 * Date     : 01.05.2012
 * Time     : 12:57:08
 * Email    : denys.astanin@gmail.com
 */

public class C {
	public static void main(String[] args) throws IOException {
		new C().run();
	}

	int nextInt() throws IOException {
		in.nextToken();
		return (int) in.nval;
	}

	String nextString() throws IOException {
		in.nextToken();
		return (String) in.sval;
	}

	StreamTokenizer in;
	Writer writer;
	Reader reader;

	void run() throws IOException {
		boolean oj = System.getProperty("ONLINE_JUDGE") != null;
		reader = oj ? new InputStreamReader(System.in, "ISO-8859-1")
				: new FileReader("src/vk_cup_round2/C.txt");
		writer = new OutputStreamWriter(System.out, "ISO-8859-1");
		in = new StreamTokenizer(new BufferedReader(reader));
		PrintWriter out = new PrintWriter(writer);
		String s = nextString();
		String t = nextString();
		int mod = 1000000007;
		int result = 0;
		int[][] dp = new int [s.length() + 1][t.length() + 1];
		for (int i = 0; i < s.length(); i++) {
			for (int j = 0; j < t.length(); j++) {
				dp[i + 1][j + 1] = (dp[i + 1][j] + (t.charAt(j) == s.charAt(i) ? 1 : 0) * (dp[i][j] + 1)) % mod;
			}
		}
		for (int i = 0; i < s.length(); i++) {
			result = (result + dp[i + 1][t.length()]) % mod;
		}
		out.println(result);
		out.flush();
		out.close();
	}
}
