#include<stdio.h>
#include<string.h>
#define N 666013
#define M 505
char x[M],y[M],c;
long i,j,n,m,s[M][M],r[M][M],u[M][27],v[M][27],t;

long max(long a,long 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;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(x[i-1]==y[j-1]&&u[i-1][x[i-1]-'a']!=i-1&&v[j-1][y[j-1]-'a']!=j-1)
     r[i][j]-=r[u[i-1][x[i-1]-'a']][v[j-1][y[j-1]-'a']];
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(t<r[i][j])
     t=r[i][j];
fprintf(g,"%ld",t);
return 0;}