#include<fstream>
#include<cstring>
using namespace std;

ifstream fin("subsir.in");
ofstream fout("subsir.out");

int len[505][505], no[505][505];

int main()
{  int n,m,i,j,poz;
   char s1[505], s2[505], r;
   fin>>(s1+1);
   fin>>(s2+1);
   m = strlen(s1+1);
   n = strlen(s2+1);
   for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
      {
        if(s1[j] == s2[i])
         {
           len[i][j]=len[i-1][j-1] + 1;
           if(len[i][j] == 1)
            no[i][j] = 1;
           else
            no[i][j] = no[i-1][j-1];
         }
        else
          if(len[i-1][j]>len[i][j-1])
              {
                len[i][j]=len[i-1][j];
                no[i][j] = no[i-1][j];
              }
          else
           if(len[i-1][j]<len[i][j-1])
           {
             len[i][j] = len[i][j-1];
             no[i][j] = no[i][j-1];
           }
           else
           {
            len[i][j] = len[i][j-1];
            no[i][j] = (no[i][j-1] + no[i-1][j]) % 666013;
            if(len[i][j-1]==len[i-1][j-1])
              no[i][j] = (no[i][j] - no[i-1][j-1] + 666013) % 666013;
           }

      }
//
//      for(i=1;i<=n;i++)
//      {
//          for(j=1;j<=m;j++)
//            fout<<len[i][j]<<' ';
//
//       fout<<"\n";
//      }
//     fout<<"\n";
//     for(i=1;i<=n;i++)
//      {
//          for(j=1;j<=m;j++)
//            fout<<no[i][j]<<' ';
//
//       fout<<"\n";
//      }

     fout<<no[n][m];
//    poz=len[n][m];
//    fout<<poz<<endl;
//    for(i=n,j=m;poz;)
//      if(s1[j]==s2[i]) { r[poz--]=s1[j]; j--;i--; }
//      else if(len[i-1][j]==len[i][j]) i--;
//           else if (len[i][j-1]==len[i][j]) j--;
//    for(i=1;i<=len[n][m];i++)
//      fout<<r[i]<<' ';
     fin.close();
     fout.close();
    return 0;

}