#include <bits/stdc++.h>

using namespace std;

const int NMAX = 501;
const int MOD = 666013;
char sir1[NMAX],sir2[NMAX];
long long int table[NMAX][NMAX];
long long int maxx = -1;
long long int nr = 0;

int main()
{
   ifstream in("subsir.in");
   ofstream out("subsir.out");
  in>>(sir1+1)>>(sir2+1);
  in.close();
   int length1 = strlen(sir1+1);
   int length2 = strlen(sir2+1);
   for(int i=1;i<=length1;i++)
    for(int j=1;j<=length2;j++)
        if(sir1[i]==sir2[j])
            {
                table[i][j] = table[i-1][j-1]+1;
                if(maxx<table[i][j])
                    maxx = table[i][j];
            }
        else
            table[i][j] = max(table[i-1][j],table[i][j-1]);
    for(int i=1;i<=length1;i++)
      for(int j=1;j<=length2;j++)
        if((table[i][j]==maxx) && (max(table[i-1][j],table[i][j-1])<maxx))
                nr = (nr + 1) % MOD;
        out<<nr<<'\n';
        out.close();
}