PCK2016-yo-7.cpp

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int mod=1000000007;
int dp[1001][1001];

string S,T;

inline void add(int &a,int b){
    a+=b;
    if(a>=mod)a-=mod;
}
signed main(){
    cin>>S>>T;

    dp[0][0]=1;
    int N=S.size();
    int M=T.size();

    for(int i=0;i<=N;i++){
        for(int j=0;j<=M;j++){
            if(i<N)add(dp[i+1][j],dp[i][j]);
            if(i<N&&j<M&&S[i]==T[j]){
                add(dp[i+1][j+1],dp[i][j]);
            }
        }
    }

    cout<<dp[N][M]<<endl;
    return 0;
}