#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<climits>
#include<set>
#include<tuple>
#include<stack>


using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpl;
int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };

#define ARRAY_MAX 1005

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;

ll dp[ARRAY_MAX][ARRAY_MAX];

string s, t;
ll s_len, t_len;


ll dfs(ll snow,ll tnow) {

	//文字列sのsnow文字、文字列tのtnow文字まで見た時にsの部分列に含まれるtの個数

	if (dp[snow][tnow] != -1)
	{
		//既に調べてある
		return dp[snow][tnow];
	}

	if (tnow == 0)
	{
		//最後まで見られた
		return 1LL;
	}

	if (snow == 0)
	{
		if (tnow == 0)
		{
			//部分文字列になった
			return 1LL;
		}
		else
		{
			//最後まで見たけど部分文字列にならなかった
			return 0LL;
		}
	}


	//以下次の遷移

	ll cnt = 0;
	if (s[snow] == t[tnow])
	{
		cnt += dfs(snow - 1, tnow - 1);//sのsnow番目の文字を採用する場合
		cnt %= MOD;
		cnt += dfs(snow - 1, tnow);//sのsnow番目の文字を採用しない場合
		cnt %= MOD;
	}
	else
	{
		//今見ている文字が一致していない場合
		//一致するまではここ
		cnt += dfs(snow - 1, tnow);
		cnt %= MOD;
	}

	return dp[snow][tnow] = cnt;
}



int main() {

	cin >> s >> t;
	s = " " + s;
	t = " " + t;
	s_len = s.size();
	t_len = t.size();

	if (s_len < t_len)
	{
		cout << "0" << endl;
	}
	else
	{
		for (int i = 0; i < ARRAY_MAX; i++)
		{
			for (int j = 0; j < ARRAY_MAX; j++)
			{
				dp[i][j] = -1;
			}
		}
		cout << dfs(s_len, t_len) << endl;
	}

	return 0;
}

### Prompt

Create a solution in cpp for the following problem:

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<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<climits>
#include<set>
#include<tuple>
#include<stack>


using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpl;
int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };

#define ARRAY_MAX 1005

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;

ll dp[ARRAY_MAX][ARRAY_MAX];

string s, t;
ll s_len, t_len;


ll dfs(ll snow,ll tnow) {

	//文字列sのsnow文字、文字列tのtnow文字まで見た時にsの部分列に含まれるtの個数

	if (dp[snow][tnow] != -1)
	{
		//既に調べてある
		return dp[snow][tnow];
	}

	if (tnow == 0)
	{
		//最後まで見られた
		return 1LL;
	}

	if (snow == 0)
	{
		if (tnow == 0)
		{
			//部分文字列になった
			return 1LL;
		}
		else
		{
			//最後まで見たけど部分文字列にならなかった
			return 0LL;
		}
	}


	//以下次の遷移

	ll cnt = 0;
	if (s[snow] == t[tnow])
	{
		cnt += dfs(snow - 1, tnow - 1);//sのsnow番目の文字を採用する場合
		cnt %= MOD;
		cnt += dfs(snow - 1, tnow);//sのsnow番目の文字を採用しない場合
		cnt %= MOD;
	}
	else
	{
		//今見ている文字が一致していない場合
		//一致するまではここ
		cnt += dfs(snow - 1, tnow);
		cnt %= MOD;
	}

	return dp[snow][tnow] = cnt;
}



int main() {

	cin >> s >> t;
	s = " " + s;
	t = " " + t;
	s_len = s.size();
	t_len = t.size();

	if (s_len < t_len)
	{
		cout << "0" << endl;
	}
	else
	{
		for (int i = 0; i < ARRAY_MAX; i++)
		{
			for (int j = 0; j < ARRAY_MAX; j++)
			{
				dp[i][j] = -1;
			}
		}
		cout << dfs(s_len, t_len) << endl;
	}

	return 0;
}

```