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