#include <fstream>
using namespace std;
ifstream fin ("subsir.in");
ofstream fout("subsir.out");
#define MOD 666013
int D[501][501],i,j,n,m,sol[501][501];
string a,b;
int main()
{
    fin>>a>>b;
    n=a.size();
    m=b.size();
    for(i=n+1;i>=1;i--)
        a[i]=a[i-1];
    a[0]=0;
    for(i=m+1;i>=1;i--)
        b[i]=b[i-1];
    b[0]=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            if(a[i]==b[j])
            {
                D[i][j]=D[i-1][j-1]+1;
                sol[i][j]=max(sol[i-1][j-1],1);
            }
            else
            {
                D[i][j]=max(D[i][j-1],D[i-1][j]);
                if(D[i][j]==D[i-1][j])
                    sol[i][j]=(sol[i][j]+sol[i-1][j])%MOD;
                if(D[i][j]==D[i][j-1])
                    sol[i][j]=(sol[i][j]+sol[i][j-1])%MOD;
                if(D[i][j]==D[i-1][j-1]&&D[i-1][j]==D[i][j-1])
                    sol[i][j]=(sol[i][j]-sol[i-1][j-1]+MOD)%MOD;
            }
        }
    fout<<sol[n][m];
    return 0;
}