# include <fstream>
# include <cstring>
# define MOD 666013
using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");
char a[505],b[505];
int d[505][505],v[505][505],n,m,i,j;
int main () {
    fin>>a+1>>b+1;
    n=strlen(a+1);
    m=strlen(b+1);
    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];
                if(d[i][j]==0)
                    d[i][j]++;
                v[i][j]=v[i-1][j-1]+1;
                if(d[i][j]>=MOD)
                    d[i][j]-=MOD;
            }
            else{
                if(v[i][j-1]==v[i-1][j]){
                    d[i][j]=d[i-1][j]+d[i][j-1];
                    v[i][j]=v[i-1][j];
                    if(d[i][j]>=MOD)
                    d[i][j]-=MOD;
                }
                else{
                    if(v[i][j-1]>v[i-1][j]){
                        v[i][j]=v[i][j-1];
                        d[i][j]=d[i][j-1];
                    }
                    else{
                        v[i][j]=v[i-1][j];
                        d[i][j]=d[i-1][j];
                    }
                }
            }
    fout<<d[n][m]<<"\n";
    return 0;
}