#include <iostream>
#include <fstream>
#include <cstring>


using namespace std;
ifstream f("subsir.in");
ofstream g("subsir.out");
int maxim[505][505],cnt[505][505],n,m,mod=666013;
char a[505],b[505];
int main()
{
f>>a+1;
f>>b+1;
int n=strlen(a+1);
int m=strlen(b+1);
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=m;j++)
    {if(a[i]==b[j]) maxim[i][j]=maxim[i-1][j-1]+1;
    else
    {
        maxim[i][j]=max(maxim[i-1][j],maxim[i][j-1]);
    }

    }
}
for(int i=0;i<=n;i++)
{
    cnt[i][0]=1;
}
for(int i=0;i<=m;i++)
{
    cnt[0][i]=1;
}
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=m;j++)
    {
        if(a[i]==b[j])
        {
            cnt[i][j]=cnt[i-1][j-1]%mod;
        }
        else
        {
            if(maxim[i][j]==maxim[i-1][j]) cnt[i][j]+=cnt[i-1][j];
            if(maxim[i][j]==maxim[i][j-1]) cnt[i][j]+=cnt[i][j-1];
            if(maxim[i][j]==maxim[i-1][j-1]) cnt[i][j]-=cnt[i-1][j-1];
            cnt[i][j]+=mod;
            cnt[i][j]=cnt[i][j]%mod;
        }
    }
}
g<<cnt[n][m];

}