#include <bits/stdc++.h>

using namespace std;

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

int main()
{
   freopen("subsir.in","r",stdin);
   freopen("subsir.out","w",stdout);
   gets(sir1+1);
   gets(sir2+1);
   fclose(stdin);
   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;
    printf("%d",nr);
   fclose(stdout);
}