#include<stdio.h>
#include<string.h>
#define N 666013
#define M 505
char x[M],y[M],c;
long i,j,n,m,s[M][M],r[M][M],u[M][27],v[M][27];
int main()
{FILE *f=fopen("subsir.in","r"),*g=fopen("subsir.out","w");
fgets(x,M,f),fgets(y,M,f);
n=strlen(x)-1;
m=strlen(y)-1;
for(i=n;i;i--)
     x[i]=x[i-1];
for(i=m;i;i--)
     y[i]=y[i-1];
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
     {if(x[i]==y[j])
             s[i][j]=s[i-1][j-1]+1;
     else
             s[i][j]=s[i-1][j-1];
     if(s[i][j]<s[i-1][j])
             s[i][j]=s[i-1][j];
     if(s[i][j]<s[i][j-1])
             s[i][j]=s[i][j-1];}
for(c='a';c<='z';c++)
     {for(i=1;i<=n;i++)
     if(x[i]==c)
             u[i][c-'a']=i;     
     else
             u[i][c-'a']=u[i-1][c-'a'];
     for(i=1;i<=m;i++)
     if(y[i]==c)
             v[i][c-'a']=i;
     else
             v[i][c-'a']=v[i-1][c-'a'];}
for(i=1;i<=n;i++)
if(x[i]==y[1])
     r[i][1]=1;
for(i=2;i<=m;i++)
if(x[1]==y[i])
     r[1][i]=1;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(x[i]==y[j])
     for(c='a';c<='z';c++)
     if(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']])%N;
fprintf(g,"%ld",r[n][m]);
return 0;}