#include <fstream>
#include <string>
using namespace std;
const int p=666013;
string A,B;
int n,m,sol,L;
int c[501][501],nr[501][501];
ifstream f("subsir.in");
ofstream g("subsir.out");
int max(int x,int y){
    return x>y?x:y;
    }
int pa[501][27],pb[501][27];
int main(){
    char ch;
    int i,j,ii,jj;
    getline(f,A);
    n=A.size();
    getline(f,B);
    m=B.size();
    if (A[0]==B[0]) c[0][0]=1;
    for (i=1;i<n;++i) 
      if (A[0]==B[i]) c[0][i]=1;
        else c[0][i]=c[0][i-1];
    for (i=1;i<m;++i) 
      if (B[0]==A[i]) c[i][0]=1;
        else c[i][0]=c[i-1][0];
    for (i=1;i<n;++i)
     for (j=1;j<m;++j)
      if (A[i]==B[j]) c[i][j]=1+c[i-1][j-1];
        else c[i][j]=max(c[i-1][j],c[i][j-1]);
    L=c[n-1][m-1];

    for (ch='a';ch<='z';++ch){
        if (A[0]==ch) pa[0][ch-'a']=0;
          else pa[0][ch-'a']=-1;
        for (i=1;i<n;++i) 
         if (A[i]==ch) pa[i][ch-'a']=i;
           else pa[i][ch-'a']=pa[i-1][ch-'a'];
           }
    for (ch='a';ch<='z';++ch){
        if (B[0]==ch) pb[0][ch-'a']=0;
          else pb[0][ch-'a']=-1;
        for (i=1;i<m;++i) 
         if (B[i]==ch) pb[i][ch-'a']=i;
           else pb[i][ch-'a']=pb[i-1][ch-'a'];
           }
   
    for (i=0;i<n;++i)
     for (j=0;j<m;++j)
      if (A[i]==B[j]){
       if (c[i][j]==1 || i==0 || j==0) nr[i][j]=1;
        else 
        for (ch='a';ch<='z';++ch){
            ii=pa[i-1][ch-'a'];
            jj=pb[j-1][ch-'a'];
            if (ii>=0 && jj>=0)
             if (c[i][j]==c[ii][jj]+1) 
              nr[i][j]=(nr[i][j]+nr[ii][jj])%p;
            }
      ch=A[i]-'a';
      ii=pa[n-1][ch];
      jj=pb[m-1][ch];
      if (ii==i && jj==j) 
       if (c[i][j]==L) 
        sol=(sol+nr[i][j])%p;
      }    
    g<<sol;
    return 0;
}