#include<fstream.h>  
    #include<string.h>  
      
    int max(int a,int b)  
        {  
        if (a<b) return b;  
            else return a;  
        }  
      
   struct matrice {  
              int q,p;  
              };  
     
   int main()  
   {  
   ifstream f("subsir.in");  
   char s1[510],s2[510];  
   int i,j,k,a[511][511],n,m; long nr[511][511];  
   f>>s1>>s2;  
   f.close();  
   n=strlen(s2);m=strlen(s1);  
   for (i=0;i<=n;i++) a[i][0]=0; for (i=1;i<=m;i++) a[0][i]=0;  
   for (i=1;i<=n;i++)  
       for (j=1;j<=m;j++)  
           if (s2[i-1]==s1[j-1]) a[i][j]=1+a[i-1][j-1];  
               else a[i][j]=max(a[i][j-1],a[i-1][j]);  
   memset(nr,0,sizeof(nr));int sw,c;  
   matrice v[31][511];  
   memset(v,0,sizeof(v));  
   for (i=1;i<=26;i++)  
       for (j=1;j<=m;j++)  
           if (s1[j-1]==char(i-1+(int)'a')) v[i][j].p=j;  
               else v[i][j].p=v[i][j-1].p;  
   for (i=1;i<=26;i++)  
       for (j=1;j<=n;j++)  
           if (s2[j-1]==char(i+(int)'a'-1)) v[i][j].q=j;  
               else v[i][j].q=v[i][j-1].q;  
   for (i=1;i<=n;i++)  
       for (j=1;j<=m;j++)  
         if (s2[i-1]==s1[j-1])  
           {  
           sw=0;  
           for (k=1;k<=26;k++)  
               if (v[k][i-1].q!=0 && v[k][j-1].p!=0) {  
                                     sw=1;  
				     if (a[i][j]==1+a[v[k][i-1].q][v[k][j-1].p]) nr[i][j]=(nr[i][j]+nr[v[k][i-1].q][v[k][j-1].p])%666013;
				     }
	   if (!sw) nr[i][j]=1;
	   }
   long long nr1=0;
   for (i=1;i<=n;i++)
       for (j=1;j<=m;j++)
	   if (s1[j-1]==s2[i-1] && a[i][j]==a[n][m]) {
				 sw=1;
				 for (k=i;k<n;k++)
				   if (s2[i-1]==s2[k]) sw=0;
				 for (k=j;k<m;k++)
				   if (s1[j-1]==s1[k]) sw=0;
				 if (sw) nr1=(nr1+nr[i][j])%666013;
				 }
   ofstream g("subsir.out");
   g<<nr1;
   g.close();
   return 0;
   }