#include<iostream>  
#include<string>  
using namespace std;  

int a[501][501];  
int ps1[27][501];  
int ps2[27][501];  
int nr[501][501];  
bool mask[27];  

int main(void)  
{  
   freopen("subsir.in", "r", stdin);  
   freopen("subsir.out", "w", stdout);  
   string s1;  
   string s2;  
   cin >> s1 >> s2;  
   int l1 = s1.length();  
   int l2 = s2.length();  
   for(int i=0;i<=l1;++i)  
       a[i][0] = 0;  
   for(int i=0;i<=l2;++i)  
       a[0][i] = 0;  
   for(int i=1;i<=l1;++i)  
   {  
       for(int j=1;j<=l2;++j)  
       {  
           if(s1.at(i-1) == s2.at(j-1))  
               a[i][j] = a[i-1][j-1] + 1;  
           else  
               a[i][j] = max(a[i-1][j], a[i][j-1]);  
       }  
   }  
 
   memset(ps1, 0, sizeof(ps1));  
   memset(ps2, 0, sizeof(ps2));  
   for(int i=0;i<=26;++i)  
   {  
       for(int j=1;j<=l1;++j)  
       {  
           if(s1.at(j-1) == 'a'+i)  
               ps1[i][j] = j;  
           else  
               ps1[i][j] = ps1[i][j-1];  
       }  
       for(int j=1;j<=l2;++j)  
       {  
           if(s2.at(j-1) == 'a'+i)  
               ps2[i][j] = j;  
           else  
               ps2[i][j] = ps2[i][j-1];  
       }  
   }  
 
   memset(nr, 0, sizeof(nr));  
   for(int i=1;i<=l1;++i)  
   {  
       for(int j=1;j<=l2;++j)  
       {  
           if(s1.at(i-1) == s2.at(j-1))   
           {  
			   if(a[i][j] == 1)
			   {
				   nr[i][j] = 1;
			   }
			   else
			   {
               //bool proc = false;  
				for(int k=0;k<=26;++k)  
				{  
					if(ps1[k][i-1] != 0 && ps2[k][j-1] != 0)  
					{  
						if(a[i][j] == a[ps1[k][i-1]][ps2[k][j-1]] + 1)  
						{  
						//	proc = true;  
							nr[i][j] += nr[ps1[k][i-1]][ps2[k][j-1]]%666013;  
							nr[i][j] %= 666013;  
						}  
					}  
				}  
               //if(!proc)  
               //    nr[i][j] = 1;  
			   }
           }  
       }  
   }  
     
   memset(mask, false, sizeof(mask));  
   int n = 0;  

   for(int i=1;i<=l1;++i)  
   {  
       for(int j=1;j<=l2;++j)  
       {  
           if(a[i][j] == a[l1][l2] && s1.at(i-1) == s2.at(j-1))  
           {  
          //     if(!mask[s1.at(i-1)-'a'])   
          //     {  
          /*       bool proc = true; 
                   for(int k=i+1;k<=l1;++k) 
                       if(s1.at(i-1) == s1.at(k-1)) 
                           proc = false; 
                   for(int k=i+1;k<=l2;++k) 
                       if(s2.at(i-1) == s2.at(k-1)) 
                           proc = false; 

                   if(proc) 
                  { 
	           */       
				    if(ps1[s1.at(i-1)-'a'][l1] == i && ps2[s2.at(j-1)-'a'][l2] == j)
					{
						n += nr[i][j]%666013;  
						n %= 666013;  
					}
            //   }  
             //         mask[s1.at(i-1)-'a'] = true;  
		   }
	   }
   } 

  cout << n << endl;  
  return 0;  
}