# include <fstream>
# include <vector>
# include <cstring>

using namespace std;

# define input "subsir.in"
# define output "subsir.out"

# define MAX 502
# define mod 666013
# define max(a,b) (a>b?a:b)

vector < vector < long > > x,y;
long i,j,n,m,a[MAX][MAX],b[MAX][MAX],val,k;
char s1[MAX],s2[MAX];

bool u[27];

int main()
{
	ifstream fin ( input ) ;
	ofstream fout ( output ) ;

	fin.getline(s1,MAX);
	fin.getline(s2,MAX);
 
    n = strlen(s1);
    m = strlen(s2);
    
    x.resize(n);
    y.resize(n);
    
    for(i=1;i<=n;i++)
       for(j = 1 ;j <= m ; j ++)
       {
             if(s1[i-1] == s2[j-1])
             {
                a[i][j] = a[i-1][j-1]+1;
                val = 0;
                if(a[i][j] == 1)
                 val = 1;
                 long p = a[i][j]-1;
                 memset(u,0,sizeof(u));
                for(k=x[p].size()-1;k>=0;k--)
                {
                   if(x[p][k] < i && y[p][k] < j && !u[ s1[x[p][k] -1 ] - 'a'])
                   {
                     u[ s1[x[p][k]-1] - 'a'] = true;
                     val+=b[x[p][k]][y[p][k]];
                   }
                }
                b[i][j] = val%mod;
                x[a[i][j]].push_back(i);
                y[a[i][j]].push_back(j);
             }
             else
             {
                 a[i][j] = max(a[i-1][j],a[i][j-1]);
             }
       }
    val = 0;   
    long p = a[n][m];
    memset(u,0,sizeof(u));
    for(k=x[p].size()-1;k>=0;k--)
    {
        if(!u[ s1[x[p][k] -1 ] - 'a'])
        {
            u[ s1[x[p][k]-1] - 'a'] = true;
            val+=b[x[p][k]][y[p][k]];
        }
    }   
    val%=mod;
    
    fout << val << "\n";
    
 /*
     for(i=1;i<=n;i++)
     {
        for(j=1;j <= m; j ++)
          fout << a[i][j] <<" ";
        fout << "\n";
     }
   	*/
	return 0;
}