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

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


int main()
{
    int m,n,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]=sz[i-1][j-1]+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][j]=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]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}