#include<fstream>
#include<cstring>
using namespace std;
ifstream f("subsir.in");
ofstream g("subsir.out");
int n,m,i,j,k,l,o,c[501][501],nr[501][501];
char a[501],b[501];

int main()
{
 f.getline(a+1,501); n=strlen(a+1);
 f.getline(b+1,501); m=strlen(b+1);

 for(i=0;i<=n;i++) nr[i][0]=1;
 for(j=0;j<=m;j++) nr[0][j]=1;

 for(i=1;i<=n;i++)
 for(j=1;j<=m;j++)
 if(a[i]==b[j])
   {
     c[i][j]=c[i-1][j-1]+1;
     nr[i][j]=nr[i-1][j-1];
   }
 else if(c[i-1][j]>c[i][j-1])
 {
     c[i][j]=c[i-1][j];
     nr[i][j]=nr[i-1][j];
 }
 else if(c[i][j-1]>c[i-1][j])
 {
     c[i][j]=c[i][j-1];
     nr[i][j]=nr[i][j-1];
 }
 else
 {
     c[i][j]=c[i-1][j];
     nr[i][j]=(nr[i][j-1]+nr[i-1][j])%666013;
     if(c[i-1][j-1]==c[i-1][j]) nr[i][j]=((nr[i][j]-nr[i-1][j-1])+666013)%666013;
 }

 g<<nr[n][m];

 return 0;
}