#include<fstream>
#include<string>
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;
   fin>>s2;
   n = strlen(s1);
   m = strlen(s2);
   for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
      {
        if(s1[j + 1]==s2[i + 1])
         {
           len[i][j]=len[i-1][j-1] + 1;
           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
          {
           len[i][j] = len[i][j-1];
           no[i][j] = no[i][j-1];
          }
          if(no[i][j-1] == no[i-1][j])
            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-1][j-1];
          if(len[i][j] == 1)
            no[i][j] = 1;
      }


     fout<<no[n][m];
     fin.close();
     fout.close();
    return 0;

}