#include<cstdio>
#include<cstring>

using namespace std;

const int nmax=505;
const int mod=666013;

char a[nmax],b[nmax];
int m[nmax][nmax],f[nmax][nmax],val;
bool d[nmax][nmax];

inline int max(int a,int b)
{
    if(a>b)
        return a;
    return b;
}

int main()
{
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    int n,i,j,lng2;
    gets(a+1);
    gets(b+1);
    n=strlen(a+1);
    lng2=strlen(b+1);
    for(i=n;i;--i)
        for(j=lng2;j;--j)
            if(a[i]==b[j])
                m[i][j]=1+m[i+1][j+1],d[i][j]=1;
            else
                m[i][j]=max(m[i+1][j],m[i][j+1]);
    for(i=n;i;--i)
        for(j=lng2;j;--j)
        {
            val=m[i][j];
            if(d[i][j])
            {
                if(f[i+1][j+1]==0)
                    f[i][j]=1;
                else
                    f[i][j]=f[i+1][j+1];
                continue;
            }
            if(m[i][j+1]==val)
            {
                f[i][j]+=f[i][j+1];
                f[i][j]%=mod;
            }
            if(m[i+1][j]==val)
            {
                f[i][j]+=f[i+1][j];
                f[i][j]%=mod;
            }
            if(m[i+1][j+1]==val)
            {
                f[i][j]-=f[i+1][j+1];
                f[i][j]+=mod;
                f[i][j]%=mod;
            }
        }
    printf("%d",f[1][1]);
}