#include<cstdio>
#include<cstring>
char x[503],y[503],c;
int i,j,n,m,s[503][503],r[503][503],u[503][27],v[503][27],t,a,b;
int main()
{freopen("subsir.in","r",stdin),freopen("subsir.out","w",stdout);
gets(x),gets(y),n=strlen(x),m=strlen(y);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
     s[i][j]=(a=s[i-1][j]>s[i][j-1]?s[i-1][j]:s[i][j-1])>(b=s[i-1][j-1]+((x[i-1]==y[j-1])?1:0))?a:b;
for(c='a';c<='z';c++)
     {for(i=1;i<=n;i++)
             u[i][c-'a']=(x[i-1]==c)?i:u[i-1][c-'a'];
     for(i=1;i<=m;i++)
             v[i][c-'a']=(y[i-1]==c)?i: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++)
for(c='a';c<='z';c++)
if(x[i-1]==y[j-1]&&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']])%666013;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(i==u[n][x[i-1]-'a']&&j==v[m][y[j-1]-'a']&&s[i][j]==s[n][m])
     t=(t+r[i][j])%666013;
printf("%d",t);
return 0;}