#include<stdio.h>
#include<string.h>
#define N 666013
char x[501],y[501];
long i,j,n,m,s[501][501],k,l,nr[501][501]={0};
int main()
{freopen("subsir.in","r",stdin);
freopen("subsir.out","w",stdout);
scanf("%s\n%s\n",&x,&y);
n=strlen(x);
m=strlen(y);
for(i=0;i<=n;i++)
      s[i][0]=0;
for(j=0;j<=m;j++)
      s[0][j]=0;
for(i=1;i<=n;i++)
      {for(j=1;j<=m;j++)
             {s[i][j]=0;
             if(x[i-1]==y[j-1])
                      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(i=1;i<=n;i++)
      {for(j=1;j<=m;j++)
      if(x[i-1]==y[j-1])
             if(s[i][j]<=2)
                      nr[i][j]=1;
             else
                      {for(k=2;k<i;k++)
                             {for(l=2;l<j;l++)
                             if(s[k][l]+1==s[i][j])
                                    nr[i][j]=((nr[i][j]%N)+(nr[k][l]%N))%N;}}}
printf("%ld\n",nr[n][m]);
fclose(stdin);
fclose(stdout);
return 0;}