#include<stdio.h>
#include<string.h>
char x[501],y[501],c;
int i,j,n,m,s[501][501],r[501][501],u[501][27],v[501][27],t,a,b;
int main()
{
	freopen("subsir.in","r",stdin),freopen("subsir.out","w",stdout),gets(x),gets(y),n=strlen(x),m=strlen(y);
	for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            s[i][j]=(a=s[i-1][j]>s[i][j-1]?s[i-1][j]:s[i][j-1])>(b=s[i-1][j-1]+((x[i-1]==y[j-1])?1:0))?a:b;
	for(c='a';c<='z';++c) {
		for(i=1;i<=n;++i)
            u[i][c-'a']=x[i-1]==c?i:u[i-1][c-'a'];
     	for(i=1;i<=m;++i)
            v[i][c-'a']=y[i-1]==c?i:v[i-1][c-'a'];
	}
	for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            if(x[i-1]==y[j-1]&&s[i][j]==1)
                r[i][j]=1;
	for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            for(c='a';c<='z';++c)
                if(x[i-1]==y[j-1]&&s[i][j]==s[u[i-1][c-'a']][v[j-1][c-'a']]+1)
                    r[i][j]=(r[i][j]+r[u[i-1][c-'a']][v[j-1][c-'a']])%666013;
	for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            if(i==u[n][x[i-1]-'a']&&j==v[m][y[j-1]-'a']&&s[i][j]==s[n][m])
                t=(t+r[i][j])%666013;
	printf("%d",t);
	return 0;
}