# include <bits/stdc++.h>
using namespace std;
ifstream fi("subsir.in");
ofstream fo("subsir.out");
char s[505];
char sir[505];
int dp[505][505];
int v[505][505];
int main(void)
{
    int n,m;
    fi>>(s+1)>>(sir+1);
    n = strlen(s+1);
    m = strlen(sir+1);
    for (int i=0;i<n;++i) v[i][0] = 1;
    for (int i=0;i<m;++i) v[0][i] = 1;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j) if (s[i] == sir[j]) dp[i][j] = dp[i-1][j-1] + 1,v[i][j] = v[i-1][j-1];
            else if (dp[i-1][j] == dp[i][j-1])
             {
                 dp[i][j] = dp[i-1][j];
                 v[i][j] = (v[i-1][j]+v[i][j-1]) % 666013;
                 if (dp[i-1][j-1] == dp[i][j-1]) v[i][j] = (v[i][j] - v[i-1][i-1] + 666013) % 666013;
             }
            else if (dp[i-1][j] > dp[i][j-1]) dp[i][j] = dp[i-1][j],v[i][j]=v[i-1][j];
            else dp[i][j]=dp[i][j-1],v[i][j]=v[i][j-1];
    return fo << v[n][m] << '\n',0;
}