#include<stdio.h>
#include<string.h>

const int maxn = 600;

char a[maxn];
char b[maxn];
int mat[maxn][maxn];
int i;
int k;
int pos[maxn][maxn];
int c[maxn][maxn];
int d[maxn][maxn];
int n;
int m;
int j;


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);
        scanf("%s %s",a,b);
        n=strlen(a)-1;
        m=strlen(b)-1;

        for(i=0;i<=n;i++)
                for(j=0;j<=m;j++)
                {
                        if (a[i]==b[j])
                        {
                                if (i>0&&j>0) mat[i][j]=mat[i-1][j-1]+1;
                                        else
                                        {
                                                mat[i][j]=1;
                                        }
                        }
                        else
                        {
                                if (i>0&&j>0)mat[i][j]=max(mat[i-1][j],mat[i][j-1]);
                                if (i>0 && j<=0)mat[i][j]=mat[i-1][j];
                                if (i<=0&&j>0) mat[i][j]=mat[i][j-1];
                        }
                }
        for(i=1;i<=26;i++)
        {
                d[i][1]=-1;
                d[i][0]=-1;
                c[i][0]=-1;
                c[i][1]=-1;
        }
        c[a[0]-'a'+1][1]=0;

        for(i=1;i<=n;i++)
        {
                c[a[i-1]-'a'+1][i]=i-1;
                for(j=1;j<=26;j++)
                        c[j][i+1]=c[j][i];

        }
        d[b[0]-'a'+1][1]=0;
        for(j=1;j<=m;j++)
        {
                d[b[j-1]-'a'+1][j]=j-1;
                for(i=1;i<=26;i++)
                {
                        d[i][j+1]=d[i][j];
                }
        }
        for(i=0;i<=n;i++)
        {
                for(j=0;j<=m;j++)
                {
                        if (a[i]==b[j])
                        {
                                for(k=1;k<=26;k++)
                                {
                                        if (c[k][i]!=-1&&d[k][j]!=-1)
                                        {
                                                if (mat[c[k][i]][d[k][j]]==mat[i][j]-1) pos[i][j]=(pos[i][j]+pos[c[k][i]][d[k][j]])%666013;
                                        }
                                        if ((c[k][i]==-1||d[k][j]==-1)&&mat[i][j]==1) pos[i][j]=1;
                                }
                        }
                }
        }

        /*int sol = 0;
        for(i=1;i<=m;i++)
        {
                if (mat[n][i]==mat[n][m]) sol+=pos[n][i];
        } */

        printf("%d\n",pos[n][m]);
        return 0;
}