#include <fstream>
#include <string>

using namespace std;

ifstream fin("subsir.in");
ofstream fout("subsir.out");

const int mod= 666013;
const int nmax= 500;

string a, b;
int d[nmax+1][nmax+1], e[nmax+1][nmax+1];

int main(){
    fin>>a; fin>>b;
    int n= a.size(), m= b.size();

    for (int i= 0; i<=m; ++i){
        e[0][i]= 1;
    }
    for (int i= 1; i<=n; ++i){
        e[i][0]= 1;
        for (int j= 1; j<=m; ++j){
            if (a[i-1]==b[j-1]){
                d[i][j]= d[i-1][j-1]+1;
            }else{
                d[i][j]= max(d[i-1][j], d[i][j-1]);
            }

            if (a[i-1]==b[j-1]){
                e[i][j]= e[i-1][j-1];
            }else{
                e[i][j]= 0;
                if (d[i][j]==d[i-1][j]){
                    e[i][j]= (e[i][j]+e[i-1][j]) %mod;
                }
                if (d[i][j]==d[i][j-1]){
                    e[i][j]= (e[i][j]+e[i][j-1]) %mod;
                }
                if (d[i][j]==d[i-1][j-1]){
                    e[i][j]= (e[i][j]-e[i-1][j-1] +mod) %mod;
                }
            }
        }
    }

    fout<<e[n][m]<<"\n";

    return 0;
}