A. Substring and Subsequence

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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 ass = 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 sequencesp 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).

Sample test(s)

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]".

The state of the dp is dp[i][j] , that stands for 

every subset in i to j of string s we try to find the number of subsequences in j to |t| of string t

the recurrence can be derived as f(i,j)=1+f(i+1,j+1) if s[i]==t[j]

                                       else f(i+1,j+1)

First go through the recusrsive code

   let us take two examples 

     

           s=abcd

           t=babc

      so first we have s[0]=a 

       Now we iterate j from 0 to |t| for occurence of a , as soon as we 

get one we call go(i+1,j+1) 

           here we have a pick or leave situation  

           where we add res=go(i,j+1)  that is we search everywhere for the same character

      after we have done for all the occurences we go to call go(i+1,j+1). 

int the example above after getting all occurences of a in the string t we move for occurences of b in string t 

Code goes here

#include <cstdio>

#include <numeric>

#include <iostream>

#include <vector>

#include <set>

#include <cstring>

#include <string>

#include <map>

#include <cmath>

#include <ctime>

#include <algorithm>

#include <bitset>

#include <queue>

#include <sstream>

#include <deque>

using namespace std;

#define mp make_pair

#define pb push_back

#define rep(i,n) for(int i = 0; i < (n); i++)

#define re return

#define fi first

#define se second

#define sz(x) ((int) (x).size())

#define all(x) (x).begin(), (x).end()

#define sqr(x) ((x) * (x))

#define sqrt(x) sqrt(abs(x))

#define y0 y3487465

#define y1 y8687969

#define fill(x,y) memset(x,y,sizeof(x))

                         

typedef vector<int> vi;

typedef long long ll;

typedef long double ld;

typedef double D;

typedef pair<int, int> ii;

typedef vector<ii> vii;

typedef vector<string> vs;

typedef vector<vi> vvi;

template<class T> T abs(T x) { re x > 0 ? x : -x; }

const int mod = 1000000000 + 7;

int n;

int m;

int was[5001][5001];

int res[5001][5001];

string s, t;

int go (int i, int j) {

    if (j == m) re 1;

    if (was[i][j]) re res[i][j];

    was[i][j] = 1;

    int cur = go (i, j + 1);  // here we are trying to find the occurences of the same character in string t

    if (s[i] == t[j]) cur = (cur + go (i + 1, j + 1)) % mod;    // here we are searching for s[i+1] 

    re res[i][j] = cur;                                        // in all positions of the string t hence

}                                                         //  go(i+1,j+1)

int main () {

    cin >> s >> t;

    n = sz (s);

    m = sz (t);

    int ans = 0;

    for (int i = 0; i < n; i++) 

        for (int j = 0; j < m; j++)

            if (s[i] == t[j])

                ans = (ans + go (i + 1, j + 1)) % mod;

    cout << ans << endl;

    return 0;

}