#include <stdio.h>
#include <string.h>

using namespace std;
FILE *f,*g;
char c[1000],c1[1000];
int a[1000][1000],b[1000][1000],i,n,m,j,x;
int main()
{f=fopen ("subsir.in","r");
 g=fopen ("subsir.out","w");
 fscanf (f,"%s",&c);
 fscanf (f,"%s",&c1);
 n=strlen (c);
 m=strlen (c1);

 for (i=1;i<=m;i++)
   for (j=1;j<=n;j++)
 {
     if (c1[i-1]==c[j-1])
     {
         a[i][j]=a[i-1][j-1]+1;
         b[i][j]=b[i-1][j-1];
         if (b[i][j]==0) b[i][j]++;
         b[i][j]=b[i][j]%666013;

     }
      else
      {
          if (a[i-1][j]>a[i][j-1])
          {
              a[i][j]=a[i-1][j];
              b[i][j]=b[i-1][j];
          }
             else
          {
              a[i][j]=a[i][j-1];
              b[i][j]=b[i][j-1];
          }
          if (a[i-1][j-1]==a[i][j]) x=b[i-1][j-1];
            else x=0;
          if (a[i-1][j]==a[i][j-1]) b[i][j]+=b[i-1][j]-x;
          b[i][j]=b[i][j]%666013;
      }


 }
fprintf (g,"%d",b[m][n]);
    return 0;
}