#include <fstream>
#include <string.h>
using namespace std;

int kk = 666013;

int Len[600][600];
int Count[600][600];

char A[600],B[600];
int lA,lB;

int main(void)
{
 fstream fin("subsir.in",ios::in);
 fstream fout("subsir.out",ios::out);
 fin >> (A + 1) >> (B + 1);
 lA = strlen(A + 1);
 lB = strlen(B + 1);
 int a,b,c;

 for (a = 0;a < 600;a += 1)
  {
   Len[a][0] = 0;
   Len[0][a] = 0;
   Count[a][0] = 1;
   Count[0][a] = 1;
  }
 for (a = 1;a <= lA;a += 1)
  {
   for (b = 1;b <= lB;b += 1)
    {
     if (A[a] == B[b])
       {
        Len[a][b] = Len[a - 1][b - 1] + 1;
        Count[a][b] = Count[a - 1][b - 1];
       }
      else
       {
        if (Len[a - 1][b] == Len[a][b - 1])
          {
           Len[a][b] = Len[a][b - 1];
           Count[a][b] = (Count[a - 1][b] + Count[a][b - 1]) % kk;
           if (Len[a - 1][b - 1] == Len[a][b])
             {
              Count[a][b] = (Count[a][b] - Count[a - 1][b - 1] + kk) % kk;
             }
          }
         else
          {
           if (Len[a - 1][b] > Len[a][b - 1])
             {
              Len[a][b] = Len[a - 1][b];
              Count[a][b] = Count[a - 1][b];
             }
            else
             {
              Len[a][b] = Len[a][b - 1];
              Count[a][b] = Count[a][b - 1];
             }
          }
       }
    }
  }
 fout << (Count[lA][lB] % kk);
 fin.close();
 fout.close();
 return 0;
}