# 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=1;i<=n;++i)
    {
        int vtot = 1,lmax = 0;
        for (int j=1;j<=m;++j)
            {
                if (s[i] == sir[j])
                if (lmax == dp[i-1][j] && vtot > v[i-1][j]) dp[i][j] = lmax + 1,v[i][j] = vtot + v[i-1][j];
                else if (lmax > dp[i-1][j]) dp[i][j] = lmax + 1,v[i][j] = vtot;
                else dp[i][j] = dp[i-1][j],v[i][j] = v[i-1][j];
                int cnt = 0,gmax = 0;
                for (int x=1;x<i;++x)
                    if (gmax < dp[i-x][j]) gmax = dp[i-x][j],cnt = v[i-x][j];
                if (lmax < gmax)  lmax = gmax,vtot = cnt;else
                if (lmax == gmax) vtot = (vtot + cnt) % 666013;
            }
    }
  //  for (int i=1;i<=n;++i,cout << '\n') for (int j=1;j<=m;++j) cout << dp[i][j]<< ' ';cout << "\n\n";
  //  for (int i=1;i<=n;++i,cout << '\n') for (int j=1;j<=m;++j) cout << v[i][j] << ' ';
    return fo << v[n][m] << '\n',0;
}