#include<cstdio>
#include<cstring>
#define N 666013
#define M 505
char x[M],y[M],c;
int i,j,n,m,s[M][M],r[M][M],u[M][27],v[M][27];

int max(int a,int b)
{return a>b?a:b;}

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=1;i<=n;i++)
for(j=1;j<=m;j++)
     s[i][j]=max(max(s[i-1][j],s[i][j-1]),s[i-1][j-1]+((x[i-1]==y[j-1])?1:0));
for(c='a';c<='z';c++)
     {for(i=1;i<=n;i++)
     if(x[i-1]==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-1]==c)
             v[i][c-'a']=i;
     else
             v[i][c-'a']=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++)
if(x[i-1]==y[j-1])
     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,"%d",r[n][m]);
return 0;}