#include <bits/stdc++.h>

using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");
int c[505][505],nr[505][505];
char a[505],b[505];
int main()
{
     fin>>a;
     fin>>b;
     int i,j,n,m;
     n=strlen(a);
     m=strlen(b);
     for(i=0;i<=n;++i)
        nr[i][0]=1;
    for(i=0;i<=m;++i)
        nr[0][i]=1;

    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
        if(a[i-1]==b[j-1])
    { c[i][j]=c[i-1][j-1]+1;
      nr[i][j]=nr[i-1][j-1];
    }
    else if(c[i-1][j]>c[i][j-1])
    {
     c[i][j]=c[i-1][j];
     nr[i][j]=nr[i-1][j];
    }
    else if(c[i-1][j]<c[i][j-1])
    {
     c[i][j]=c[i][j-1];
     nr[i][j]=nr[i][j-1];

    }
    else
    {
     c[i][j]=c[i-1][j];
     nr[i][j]=(nr[i][j-1]+nr[i-1][j])%666013;
     if(c[i-1][j-1]==c[i-1][j] || a[i-2]==b[j-2]  ) nr[i][j]=((nr[i][j]-nr[i-1][j-1])+666013)%666013;
 }
    fout<<nr[n][m];

    return 0;
}