#include <iostream>
#include <fstream>
#include <cstring>
#define NMAX 502
#define MOD 666013
using namespace std;
char x[NMAX], y[NMAX];
int d[NMAX][NMAX], l[NMAX][NMAX], n, m, i, j;
int main()
{
    ifstream cin("subsir.in");
    ofstream cout("subsir.out");
    cin.getline(x,1000);
    cin.getline(y,1000);
    n=strlen(x);
    m=strlen(y);
    l[0][0]=1;
    for(i=1; i<=n; i++)
        l[i][0]=1;
    for(i=1; i<=m; i++)
        l[0][i]=1;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            if(x[i-1]==y[j-1])
            {
                d[i][j]=d[i-1][j-1]+1;
                l[i][j]=l[i-1][j-1];
            }
            else if(d[i][j-1]<d[i-1][j])
            {
                d[i][j]=d[i-1][j];
                l[i][j]=l[i-1][j];
            }
            else if(d[i][j-1]>d[i-1][j])
            {
                d[i][j]=d[i][j-1];
                l[i][j]=l[i][j-1];
            }
            else if(d[i][j-1]==d[i-1][j])
            {
                d[i][j]=d[i-1][j];
                l[i][j]=(l[i][j-1]+l[i-1][j])%MOD;
                if(d[i-1][j]==d[i-1][j-1])
                    l[i][j]=(l[i][j]-l[i-1][j-1])%MOD;
            }
    cout<<l[n][m]<<'\n';
    return 0;
}