#include<fstream.h>
#include<string.h>
#define g 505
using namespace std;
int c[g][g]={0},n,m;
ifstream be ("subsir.in");
ofstream ki ("subsir.out");
void read (char a[], char b[], int &n, int &m)
 {
  int i;
  be.getline(a,500,'\n');
  be.getline(b,500,'\n');
  n=strlen(a);
  m=strlen(b);
  be.close();
 }

int program (char a[], char b[])
 {
  int i,j,sz=0;
  for (i=n-1;i>=0;i--)
    for (j=m-1;j>=0;j--)
       if (a[i]==b[j])
	 c[i][j]=c[i+1][j+1]+1;
       else
	  if (c[i][j+1]>c[i+1][j])
	    c[i][j]=c[i][j+1];
	  else
	    c[i][j]=c[i+1][j];

  for (i=0;i<n;i++)
     for (j=0;j<m;j++)
       {
	if (i==0 && j==0)
	  ;
	else
	  if (c[i][j]==c[0][0] && c[i][j+1]!=c[0][0] && c[i+1][j]!=c[0][0])
	    sz++;
       }
  return sz;
 }

int main()
 {
  char a[g]={0},b[g]={0};
  read (a,b,n,m);
  int t;
  t=program (a,b);
  ki<<t%666013;
  ki<<"\n";
  ki.close();
  return 0;
 }