#include <fstream>
#include <algorithm>
#include <cstring>

using namespace std;

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

const int NMAX = 520;
const int MOD  = 666013;

char a[NMAX], b[NMAX];

int d[NMAX][NMAX], sol[NMAX][NMAX];

int main() {

    fin >> (a + 1);
    fin >> (b + 1);

    int n = strlen(a + 1);
    int m = strlen(b + 1);

    for (int i = 0; i <= n || i <= m; i++)
        sol[i][0] = sol[0][i] = 1;


    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {

            if (a[i] == b[j]){

                d[i][j] = d[i - 1][j - 1] + 1;
                sol[i][j] = sol[i - 1][j - 1];

            }
            else{
                if (d[i - 1][j] > d[i][j - 1]) {

                    d[i][j] = d[i - 1][j];
                    sol[i][j] = sol[i - 1][j];

                }
                else
                    if (d[i][j - 1] > d[i - 1][j]) {

                        d[i][j] = d[i][j - 1];
                        sol[i][j] = sol[i][j - 1];

                    }
                    else {

                        d[i][j] = d[i - 1][j];
                        sol[i][j] = sol[i - 1][j] + sol[i][j - 1];

                        if (sol[i][j] >= MOD)
                            sol[i][j] -= MOD;

                        if (d[i][j] == d[i - 1][j - 1]){
                            sol[i][j] -= sol[i - 1][j - 1];
                            if (sol[i][j] < 0)
                                sol[i][j] += MOD;
                        }
                    }
            }

        }

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

    return 0;
}