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

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

#define DIM 500
#define MOD 666013

int dp[DIM + 1][DIM + 1], nrmod[DIM + 1][DIM + 1];
char s1[DIM + 1], s2[DIM + 1];

static inline void SubSirComMax(int lg1, char s1[], int lg2, char s2[]) {
  for(int i = 1; i <= lg1; i++)
    for(int j = 1; j <= lg2; j++)
      if(s1[i - 1] == s2[j - 1]) {        //daca am 2 caractere egale cresc lungimea sirului actual;
        dp[i][j] += 1 + dp[i - 1][j - 1];

        if(!nrmod[i - 1][j - 1])
          nrmod[i][j] = 1;        //daca e prima data cand obtin sirul actual;
        else  nrmod[i][j] = nrmod[i - 1][j - 1];     

      }else {
        if(dp[i - 1][j] > dp[i][j - 1]) { //iau vecinul maxim;
          dp[i][j] = dp[i - 1][j];
          nrmod[i][j] = nrmod[i - 1][j];
        }else if(dp[i - 1][j] < dp[i][j - 1]) {
          dp[i][j] = dp[i][j - 1];
          nrmod[i][j] = nrmod[i][j - 1];
        }else {                 //daca sunt egale;
          dp[i][j] = dp[i - 1][j];
          nrmod[i][j] = (nrmod[i - 1][j] + nrmod[i][j - 1]) % MOD;    //iau toate modurile posibile
          if(dp[i - 1][j] == dp[i - 1][j - 1])
            nrmod[i][j] = (nrmod[i][j] - nrmod[i - 1][j - 1] + MOD) % MOD;  //scad modurile care sunt de mai multe ori;
        }
      }
}

int main() {
  int lg1, lg2; 

  fin >> s1 >> s2;
  lg1 = strlen(s1);
  lg2 = strlen(s2);

  SubSirComMax(lg1, s1, lg2, s2);
  fout << nrmod[lg1][lg2];
  
  return 0;
}