#include <cstdio>
#include <cstring>
#define Mod 666013

using namespace std;
char s[505],t[505];
int n,m,i,j,d[505][505],x[505][505];

int main()
{
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    scanf("%s\n%s",s+1,t+1);
    n=strlen(s+1);
    m=strlen(t+1);
    for (i=0; i<=n; i++) x[i][0]=1;
    for (j=0; j<=m; j++) x[0][j]=1;

    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
        if (s[i]==t[j])
    {
        d[i][j]=d[i-1][j-1]+1;
        x[i][j]=x[i-1][j-1];
    }
        else
            if (d[i][j-1]==d[i-1][j])
        {
            d[i][j]=d[i][j-1];
            x[i][j]=(x[i][j-1]+x[i-1][j])%Mod;
            if (d[i][j]==d[i-1][j-1])
                x[i][j]=(x[i][j]-x[i-1][j-1])%Mod;
        }
        else
            if (d[i][j-1]>d[i-1][j])
        {
            d[i][j]=d[i][j-1];
            x[i][j]=x[i][j-1];
        }
        else
        {
            d[i][j]=d[i-1][j];
            x[i][j]=x[i-1][j];
        }
    if (x[n][m]<0) x[n][m]=x[n][m]+Mod;
    printf("%d\n",x[n][m]);
    return 0;
}