#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))   
           {  
               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) 
                  { 
                     n += nr[i][j]%666013;  
                      n %= 666013;  
               }  
             //         mask[s1.at(i-1)-'a'] = true;  
              //}  
          }  
      }  
  }  
  cout << n << endl;  
  return 0;  
}