#include<algorithm>
#include<cstdio>
#include<cstring>
#define Nmax 505
using namespace std;
int v[Nmax][Nmax];
char a[Nmax],b[Nmax];
int n,i,j,m,p,x[Nmax][Nmax],y[Nmax][Nmax],Max,sol;
int ii,jj,w[Nmax][Nmax];
int ok[Nmax][Nmax];
int main()
{
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    gets(a+1); n=strlen(a+1);
    gets(b+1); m=strlen(b+1);
    for (i=1;i<=n;i++)
    for (j=1;j<=m;j++)
    if (a[i]==b[j])
    {
        v[i][j]=v[i-1][j-1]+1;
        Max=max(Max,v[i][j]);
    }else
    v[i][j]=max(v[i-1][j],v[i][j-1]);
    for (p=0;p<26;p++)
    {
        x[p][0]=-1;
        for (i=1;i<=n;i++)
        if (a[i]==p+'a') x[p][i]=i;
        else x[p][i]=x[p][i-1];
        for (i=1;i<=m;i++)
        if (b[i]==p+'a') y[p][i]=i;
        else y[p][i]=x[p][i-1];
    }
    w[0][0]=1;
    for (p=0;p<26;p++){
    for (i=1;i<=n;i++)
    for (j=1;j<=m;j++)
    if (a[i]==b[j] && !ok[v[i][j]][j])
    {
        if (v[i][j]==1) {w[i][j]=1; continue;}
            ii=x[p][i-1];
            jj=y[p][j-1];
            if (x[a[i]-'a'][i-1]>=ii || y[b[j]-'a'][j-1]>=jj)
            continue;
            if (ii==-1 || jj==-1) continue;
            if (v[ii][jj]+1==v[i][j])
            w[i][j]=(w[i][j]+w[ii][jj])%666013;
            if (v[i][j]==Max)
            sol=(sol+w[i][j])%666013;
        if (w[i][j])
        ok[v[i][j]][j]=1;
    }
    }
    printf("%d",sol);
    return 0;
}