#include<iostream> 
#include<fstream> 
#include<string.h>
using namespace std;
ifstream f("subsir.in"); ofstream g("subsir.out");
char a[501],b[501];
int c[501][501],d[501][501],i,j,n,m;
int main()
{
    f>>a+1>>b+1;
    n=strlen(a+1);
    m=strlen(b+1);
    for(i=0;i<=n;i++)
        d[i][0]=1;
    for(j=0;j<=m;j++)
        d[0][j]=1;
    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;
        d[i][j]=d[i-1][j-1];}
        else
            if(c[i-1][j]==c[i][j-1])
        {c[i][j]=c[i-1][j];
        d[i][j]=(d[i-1][j]+d[i][j-1])%666013;
        if(c[i-1][j-1]==c[i][j-1])
            d[i][j]=(d[i][j]-d[i-1][j-1]+666013)%666013;
        }
        else
            if(c[i][j-1]>c[i-1][j])
            {c[i][j]=c[i][j-1];
        d[i][j]=d[i][j-1];}
        else
        {
            c[i][j]=c[i-1][j];
            d[i][j]=d[i-1][j];
        }
        g<<d[n][m];
}