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.math.*;
import java.io.*;
public class Main
	{
	public static void main(String args[])	throws IOException
		{
		Scanner c=new Scanner(System.in);
		char A[]=c.next().toCharArray();
		char B[]=c.next().toCharArray();
		
		int N=A.length;
		int M=B.length;
		int DP[][]=new int[N][M];		//substring ending at char i, subsequence contains chars upto j
		if(A[0]==B[0])
			DP[0][0]=1;
		for(int j=1;j<M;j++) 
			{
			if(B[j]==A[0])
				DP[0][j]=1+DP[0][j-1];
			else
				DP[0][j]=DP[0][j-1];
			}
		for(int i=1;i<N;i++) 
			{
			for(int j=0;j<M;j++) 
				{
				//include B[j] in subsequence
				if(A[i]==B[j])
					{
					if(j>0)
						{
						//System.out.println("adding 1 for ("+i+","+j+")");
						DP[i][j]=1+DP[i-1][j-1];
						}
					else
						DP[i][j]=1;
					}
				//B[j] is not in the subsequence
				if(j!=0)
					DP[i][j]+=DP[i][j-1];
				DP[i][j]%=1000000007;
				}
			}
		/*for(int i=0;i<N;i++) 
			{
			System.out.println(Arrays.toString(DP[i]));
			}
		*/
		long sum=0;
		for(int i=0;i<N;i++) 
			{
			sum+=DP[i][M-1];
			}
		System.out.println(sum%1000000007);
		}
	}

//must declare new classes here