#include<stdio.h>
#include<string.h>
#define Nm 501
#define Mod 666013
#define max(a,b) ((a)>(b)?(a):(b))
char A[Nm],B[Nm];
int M[Nm][Nm],Nr[Nm][Nm],FirstA[26][Nm],FirstB[26][Nm];

void read()
{
    freopen("subsir.in","r",stdin);
    scanf("%s%s",A,B);
}

void solve()
{
    int n,m,i,j,k;

    n=strlen(A);
    m=strlen(B);

    for(j=0;j<26;j++)
	FirstA[j][n]=n;
    for(i=n-1;i>=0;i--)
    {
	for(j=0;j<26;j++)
	    FirstA[j][i]=FirstA[j][i+1];
	FirstA[A[i]-'a'][i]=i;
    }

    for(j=0;j<26;j++)
	FirstB[j][m]=m;
    for(i=m-1;i>=0;i--)
    {
	for(j=0;j<26;j++)
	    FirstB[j][i]=FirstB[j][i+1];
	FirstB[B[i]-'a'][i]=i;
    }

    for(i=0;i<=n;i++)
	Nr[i][m]=1;
    for(j=0;j<m;j++)
	Nr[n][j]=1;

    for(i=n-1;i>=0;i--)
	for(j=m-1;j>=0;j--)
	{
	    if(A[i]==B[j])
		M[i][j]=1+M[i+1][j+1];
	    else
		M[i][j]=max(M[i][j+1],M[i+1][j]);
	    if(!M[i][j])
	    {
		Nr[i][j]=1;
		continue;
	    }
	    for(k=0;k<26;k++)
		if(FirstA[k][i]<n && FirstB[k][j]<m)
		    if(M[FirstA[k][i]+1][FirstB[k][j]+1]==M[i][j]-1)
			Nr[i][j]=(Nr[i][j]+Nr[FirstA[k][i]+1][FirstB[k][j]+1])%Mod;
	}
}

void write()
{
    freopen("subsir.out","w",stdout);
    printf("%d\n",Nr[0][0]);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}