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

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(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(x[i-1]==y[j-1])
     r[i][j]=(r[i-1][j-1]+1)%N;
else
     r[i][j]=(r[i-1][j]+r[i][j-1]-r[i-1][j-1])%N;
fprintf(g,"%d",r[n][m]);
return 0;}