#include <fstream>
#include <string>

using namespace std;

const int MOD = 666013;
const int N = 505;

string x, y;
int sol, ii, jj;
int d[N][N], c[N][N];
int litx[30][N], lity[30][N];

void cmlsc(string x, string y)
{
    for (int i = 0; i < x.size(); ++i)
        for (int j = 0; j < y. size(); ++j) {
            if (x[i] == y[j])
                c[i][j] = c[i - 1][j - 1] + 1;
            else
                c[i][j] = max(c[i - 1][j], c[i][j - 1]);
            if(c[i][j] == 1 && x[i] == y[j])
                d[i][j] = 1;
        }
}

void litere(string x, int a[][N])
{
    for (int i = 0; i < x.size(); ++i)
        for (int j = 0; j < 26; ++j)
            if (x[i] - 'a' == j)
                a[j][i] = i;
            else
                a[j][i] = a[j][i - 1];
}

int main()
{
    ifstream f("subsir.in");
    ofstream g("subsir.out");
    
    f >> x >> y;

    cmlsc(x, y);
    litere(x, litx);
    litere(y, lity);

    for (int i = 0; i < x.size(); ++i)
        for (int j = 0; j < y.size(); ++j) {
            if(x[i] == y[j]) {
                for (int k = 0; k < 26; ++k) {
                    ii = litx[k][i];
                    jj = lity[k][j];
                    if(c[i][j] == c[ii][jj] + 1)
                        d[i][j] = (d[i][j] + d[ii][jj]) % MOD;
                }
            }
        }

    for (int i = 0; i < x.size(); ++i)
        for (int j = 0; j < y.size(); ++j)
            if(c[i][j] == c[x.size() - 1][y.size() - 1] && litx[x[i] - 'a'][x.size() - 1] == i && lity[y[j] - 'a'][y.size() - 1] == j)
                sol = (sol + d[i][j]) % MOD;

    g << sol;

    return 0;
}