#include<stdio.h>
#include<string.h>
char x[503],y[503],c;
int i,j,n,m,s[503][503],r[503][503],u[503][27],v[503][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);
}