#include <fstream>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;



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

string x, y, x2, y2;
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 = 1; i < x.size(); ++i)
        for (int j = 1; 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]);
        }
}

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

int main()
{
    ifstream f("subsir.in");
    ofstream g("subsir.out");
    x.push_back(' ');
    y.push_back(' ');
    f >> x2 >> y2;
    x += x2;
    y += y2;

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

    for (int i = 1; i < x.size(); ++i)
        for (int j = 1; j < y.size(); ++j) {
            if(c[i][j] == 1 && x[i] == y[j]) {
                d[i][j] = 1;
                continue;
            }
            if(x[i] == y[j]) {
                for (int k = 'a'; k <= 'z'; ++k) {
                    ii = litx[k - 'a'][i - 1];
                    jj = lity[k - 'a'][j - 1];
                    if(c[i][j] == c[ii][jj] + 1) {
                        d[i][j] = (d[i][j] % MOD + d[ii][jj] % MOD) % MOD;
                    }
                }
            }
        }
    
    for (int i = 1; i < x.size(); ++i)
        for (int j = 1; 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 % MOD + d[i][j] % MOD) % MOD;

    g << sol;

    return 0;
}