#include <cstdio>
#include <cstring>
#define MaxN 505
#define MOD 666013
#define infile "subsir.in"
#define outfile "subsir.out"

char a[MaxN],b[MaxN];
int c[MaxN][MaxN],sol[MaxN][MaxN];
int N,M;

void read()
{
      scanf("%s%s",a+1,b+1);
}

void initial()
{
      int i;
      for(i=0;i<=N;i++)
            sol[i][0]=1;
      for(i=0;i<=M;i++)
            sol[0][i]=1;
}


void solve()
{
      int i,j;
      N=strlen(a+1); M=strlen(b+1);
      initial();

      for(i=1;i<=N;i++)
            for(j=1;j<=M;j++)
            {
                  if(a[i]==b[j])
                        c[i][j]=c[i-1][j-1]+1, sol[i][j]=sol[i-1][j-1];
                  else
                        if(c[i-1][j]>c[i][j-1])
                              c[i][j]=c[i-1][j],
                              sol[i][j]=sol[i-1][j];
                        else
                              if(c[i][j-1]>c[i-1][j])
                                    c[i][j]=c[i][j-1],
                                    sol[i][j]=sol[i][j-1];
                              else
                              {
                                    c[i][j]=c[i][j-1];
                                    sol[i][j]=(sol[i-1][j]+sol[i][j-1])%MOD;
                                    if(c[i][j]==c[i-1][j-1])
                                          sol[i][j]=(sol[i][j]-sol[i-1][j-1]+MOD)%MOD;
                              }
            }

}

void write()
{
      printf("%d\n",sol[N][M]);
}

int main()
{
      freopen(infile,"r",stdin);
      freopen(outfile,"w",stdout);

      read();
      solve();
      write();

      fclose(stdin);
      fclose(stdout);
      return 0;
}