#include<fstream>
#include<cstring>
#include<algorithm>
using namespace std;
ifstream f("subsir.in");
ofstream g("subsir.out");
char ac[501],bc[501];
int a[501],b[501],i,j,n,m,c[501][501],sub[501],nr,x;
/*int distinct(int a[256],int b[256])
{
    int i,j;
    for(i=1;i<=n;i++)

}*/
int main()
{
    f.get(ac,501);
    f.get();
    f.get(bc,501);
    n=strlen(ac);
    m=strlen(bc);
    for(i=0;i<n;i++)
    a[i+1]=ac[i]-'0';
    for(j=0;j<m;j++)
    b[j+1]=bc[j]-'0';
   //for(i=1;i<=n;i++)
  // g<<a[i]<<" ";
  // g<<"\n";
   //for(j=1;j<=m;j++)
   //g<<b[j]<<" ";
   //g<<"\n";
   for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    {
        if(a[i]==b[j])
        c[i][j]=c[i-1][j-1]+1;
        else
        c[i][j]=max(c[i-1][j],c[i][j-1]);
    }
    i=n;
    j=m;
    while(c[i][j])
    {
        if(c[i][j]==c[i-1][j])
            i--;
        if(c[i][j]==c[i][j-1])
            j--;
        i--;
        j--;
    }
    nr++;
   // g<<c[n][m]<<"\n";
   g<<nr%666013;
    return 0;
}