#include <fstream>
#include <string>
 
using namespace std;
 
ifstream fin("subsir.in");
ofstream fout("subsir.out");
 
const int mod= 666013;
const int nmax= 500;
 
int d[nmax+1][nmax+1], sol[nmax+1][nmax+1];
 
int main(  ) {
    string a, b;
    fin>>a>>b;
    for ( int i= 0; i<=max((int)a.size(), (int)b.size()); ++i ) {
        sol[i][0]= sol[0][i]= 1;
    }
    for ( int i= 1; i<=(int)a.size(); ++i ) {
        for ( int j= 1; j<=(int)b.size(); ++j ) {
            if ( a[i-1]==b[j-1] ) {
                d[i][j]= d[i-1][j-1]+1;
                sol[i][j]= sol[i-1][j-1];
            } else {
                d[i][j]= max(d[i-1][j], d[i][j-1]);
                if ( d[i-1][j]>d[i][j-1] ) {
                    sol[i][j]= sol[i-1][j];
                } else {
                    sol[i][j]= sol[i][j-1];
                    if ( d[i-1][j]==d[i][j-1] ) {
                        sol[i][j]= (sol[i][j]+sol[i-1][j])%mod;
                        if ( d[i-1][j]==d[i-1][j-1] ) {
                            sol[i][j]= (sol[i][j]-sol[i-1][j-1]+mod)%mod;
                        }
                    }
                }
            }
        }
    }
 
    fout<<sol[(int)a.size()][(int)b.size()]<<"\n";
 
    return 0;
}