#include <fstream>
#include <cstdio>
#define N 505
#define MOD 666013
using namespace std;
ifstream f("subsir.in");
ofstream g("subsir.out");
long long d[N][N],n,m,l[N][N];
char a[N],b[N];
void citire ()
{ f.getline(a,504);
  while (a[n]!='\0') n++;
  f.getline(b,504);
  while(b[m]!='\0') m++;
}
void rez ()
{ int i,j;
 l[0][0]=1;
 for(i=1;i<=n;i++) l[i][0]=1;
 for(i=1;i<=m;i++) l[0][i]=1;
 for(i=1;i<=n;i++)
 for(j=1;j<=m;j++)
 if(a[i-1]==b[j-1])
 {d[i][j]=d[i-1][j-1]+1;
  l[i][j]=l[i-1][j-1];
 }
 else if(d[i-1][j]==d[i][j-1])
 { d[i][j]=d[i-1][j];
   l[i][j]=(l[i-1][j]+l[i][j-1])%MOD;
    if(d[i-1][j]==d[i-1][j-1])
    l[i][j]=(l[i][j]-l[i-1][j-1]+MOD)%MOD;
 }
 else if(d[i-1][j]>d[i][j-1])
 { d[i][j]=d[i-1][j];
   l[i][j]=l[i-1][j];
 }
 else if(d[i][j-1]>d[i-1][j])
 { d[i][j]=d[i][j-1];
   l[i][j]=l[i][j-1];
 }
}
int main()
{ citire();
  rez();
  g<<l[n][m];
  return 0;
}