#include <iostream>
#include <cstdio>
#include <cstring>
#define mod 666013
#define nmax 505
using namespace std;

char x[nmax],y[nmax];
int sz[nmax][nmax];
int rez[nmax][nmax];

int main()
{
    int n,m,i,j;
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    gets(x+1);
    gets(y+1);
    n=strlen(x+1);
    m=strlen(y+1);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(x[i]==y[j])
                sz[i][j]=1+sz[i-1][j-1];
            else sz[i][j]=max(sz[i-1][j],sz[i][j-1]);
    for(i=1;i<=n;i++)
        rez[i][1]=1;
    for(i=1;i<=m;i++)
        rez[1][i]=1;
    for(i=2;i<=n;i++)
        for(j=2;j<=m;j++)
        {
            if(x[i]==y[j])
            {
                rez[i][j]=rez[i-1][j-1];
                continue;
            }
            if(sz[i][j]==sz[i-1][j])
            {
                rez[i][j]+=rez[i-1][j];
                if(rez[i][j]>=mod)
                    rez[i][j]-=mod;
            }
            if(sz[i][j]==sz[i][j-1])
            {
                rez[i][j]+=rez[i][j-1];
                if(rez[i][j]>=mod)
                    rez[i][j]-=mod;
            }
            if(sz[i][j]==sz[i-1][j-1])
            {
                rez[i][j]-=rez[i-1][j-1];
                if(rez[i][j]<0)
                    rez[i][j]+=mod;
            }
        }
    printf("%d",rez[n][m]);
    return 0;
}