#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>0;--i)
#define yesno(flg) if(flg){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define Vi vector<int>
#define Vl vector<long long>
#define pb(a) push_back(a)
using namespace std;

typedef long long ll;
const int inf=1000000000;
const int np=1000000007;
struct edge{
	int myc,to,c,cost;
};
struct pos{
	int to,cost,color;
};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main() {
	int dp[1000]={};
	string t,b;
	cin>>t>>b;

	rep(i,t.size()){
		rrep(j,b.size()){
			if(t[i]==b[j]){
				dp[j]+=dp[j-1];
				dp[j]%=np;
			}
		}
		if(t[i]==b[0])dp[0]++;
	}
	cout<<dp[b.size()-1]<<endl;

	return 0;
}


### Prompt

Construct a cpp code solution to the problem outlined:

We, the researchers who discovered and investigated the ancient nation Iwashiro, finally discovered the temple in the center of Iwashiro. A lithograph dedicated to the god of Iwashiro was stored in the temple. On the lithograph, two strings were written, one for each sentence and one for the spell.

In Iwashiro, how many times a spell appears in a sentence has an important meaning. However, it is considered that all the characters contained in the spell appear in order, and some of them appear in the sentence in a discrete manner once. For example, if the sentence is "abab" and the spell is "ab", then "ab" appears three times in "abab", including non-continuous ones (three ways: abab, abab, and abab).

Create a program that prints how many times a spell appears in a sentence when it is given a sentence and a spell.



Input

The input is given in the following format.


t
b b


The first line is given the string t that represents the text written on the lithograph. The second line is given the string b that represents the spell written on the lithograph. Both strings are composed of only lowercase letters and have a length of 1 or more and 1000 or less.

Output

Prints how many times a spell appears in a sentence on one line. However, the value to be output can be very large, so instead output the remainder divided by 1,000,000,007.

Examples

Input

abab
ab


Output

3


Input

aaaabaaaabaaaabaaaab
aaaaa


Output

4368


Input

data
structure


Output

0

### Response

```cpp
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>0;--i)
#define yesno(flg) if(flg){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define Vi vector<int>
#define Vl vector<long long>
#define pb(a) push_back(a)
using namespace std;

typedef long long ll;
const int inf=1000000000;
const int np=1000000007;
struct edge{
	int myc,to,c,cost;
};
struct pos{
	int to,cost,color;
};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main() {
	int dp[1000]={};
	string t,b;
	cin>>t>>b;

	rep(i,t.size()){
		rrep(j,b.size()){
			if(t[i]==b[j]){
				dp[j]+=dp[j-1];
				dp[j]%=np;
			}
		}
		if(t[i]==b[0])dp[0]++;
	}
	cout<<dp[b.size()-1]<<endl;

	return 0;
}


```