#include <stdio.h>
#include <string.h>
#define NMAX 1000
#define mod 666013

char a[NMAX],b[NMAX];
int n,m;
int C[NMAX][NMAX];
int ua[NMAX][28], ub[NMAX][28];
long nr[NMAX][NMAX];
long sol;

int main()
{
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);

    fgets(a+1,1000,stdin);
    fgets(b+1,1000,stdin);
    n=strlen(a+1)-1;m=strlen(b+1)-1; 

    int i,j,ii,jj;
    char c;

    for (i=1; i<=n; ++i)
	for (j=1; j<=m; ++j)
	    if (a[i]==b[j]) C[i][j]=1+C[i-1][j-1];
	    else
		if (C[i][j-1]>C[i-1][j])
		    C[i][j]=C[i][j-1];
		else
		    C[i][j]=C[i-1][j]; 

    for (c='a'; c<='z'; ++c)
       for (j=1; j<=n; ++j) 
	   if (a[j]==c) ua[c-'a'][j]=j;
	   else ua[c-'a'][j]=ua[c-'a'][j-1];

    for (c='a'; c<='z'; ++c)
	for (j=1; j<=m; ++j)
	    if (b[j]==c) ub[c-'a'][j]=j;
	    else ub[c-'a'][j]=ub[c-'a'][j-1];

    for (i=1; i<=n; ++i)
	for (j=1; j<=m; ++j)
	    if (C[i][j]==1 && a[i]==b[j]) nr[i][j]=1;

    for (i=1; i<=n; ++i)
	for (j=1; j<=m; ++j)
	    for (c='a'; c<='z'; ++c) 
		if (a[i]==b[j]) 
		{
		    ii=ua[c-'a'][i-1];
		    jj=ub[c-'a'][j-1];
		    if (C[i][j]==C[ii][jj]+1)
			nr[i][j]=(nr[i][j]+nr[ii][jj])%mod;
		} 

    sol=0;
    for (i=1; i<=n; ++i)
	for (j=1; j<=m; ++j)
	    if (C[i][j]==C[n][m] && a[i]==b[j])
	    {
		if (ua[a[i]-'a'][n]==i && ub[b[j]-'a'][m]==j)
		    sol=(sol+nr[i][j])%mod;
	    }

    printf("%ld", sol); 

    fclose(stdin);
    fclose(stdout);

    return 0;
}