#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

const int N=1e5+;

const int MOD=1e9+;

ll dp[N][];

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    string s,t;

    cin>>s>>t;

    for(int j=;j<=s.size();j++)dp[j][]=;

    for(int i=;i<=t.size();i++)

    {

        for(int j=;j<=s.size();j++)

        {

            if(s[j-]==t[i-])dp[j][i]=(dp[j-][i]+dp[j-][i-])%MOD;

            else dp[j][i]=dp[j-][i];

        }

    }

    cout<<dp[s.size()][t.size()]<<endl;

    return     ;

}