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

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

int main()
{  int n,m,i,len[505][505]={0},no[505][505] = {0}, j;
   char s1[505], s2[505];
   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(no[i][j-1] == no[i-1][j] && no[i][j-1] == no[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];
     fin.close();
     fout.close();
    return 0;

}