//oftica si durere in suflet
#include <fstream>
#include <vector>
#include <algorithm>
#define ll long long

using namespace std;

//d[i][j][k] = cate subsiruri comune si distincte
//folosesc prefixul [1, i] din primul sir
//folosesc prefixul [1, j] din al doilea sir
//si se termina pe pozitia a[i] == b[j]
//si au lungimea k

const int MOD = 666013;
const int NMAX = 500;
const int CHR = 256;

int d[NMAX + 1][NMAX + 1];
int d2[NMAX + 1][NMAX + 1];
int s[NMAX + 1][NMAX + 1][2];

int last[NMAX + 1][2];
int fr[CHR];

//pentru un d[i][j][k] se aduna cu
//d[[last[i], i - 1]][[last[j], j - 1]][k - 1]

int sum(int i1, int i2, int j1, int j2, int k)
{
    k &= 1;
    int ans = s[i2][j2][k];
    if (i1 - 1 >= 0 and j1 - 1 >= 0)
        ans = (ans + s[i1 - 1][j1 - 1][k]) % MOD;
    if (j1 - 1 >= 0)
        ans = (ans - s[i2][j1 - 1][k] + MOD) % MOD;
    if (i1 - 1 >= 0)
        ans = (ans - s[i1 - 1][j2][k] + MOD) % MOD;
    return ans;
}

void update(int i, int j, int k)
{
    k &= 1;
    s[i][j][k] = (d[i][j]);
    s[i][j][k] = (s[i][j][k] + s[i - 1][j][k]) % MOD;
    s[i][j][k] = (s[i][j][k] + s[i][j - 1][k]) % MOD;
    s[i][j][k] = (s[i][j][k] - s[i - 1][j - 1][k] + MOD) % MOD;
}

vector <pair <int, int> > vec[NMAX + 1];
signed main()
{
    ifstream cin("subsir.in");
    ofstream cout("subsir.out");
    int i, j, k;
    int n, m;
    string a, b;
    cin >> a >> b;
    n = a.size();
    m = b.size();
    a = "!" + a;//scuze Francu
    b = "!" + b;

    for (i = 1; i <= n; i++)
    {
        last[i][0] = fr[a[i]];
        fr[a[i]] = i;
    }
    for (i = 'a'; i <= 'z'; i++)
        fr[i] = 0;
    for (i = 1; i <= m; i++)
    {
        last[i][1] = fr[b[i]];
        fr[b[i]] = i;
    }
    d[0][0] = 1;
    s[0][0][0] = 1;
    for (i = 1; i <= n; i++)
        s[i][0][0] = 1;
    for (j = 1; j <= m; j++)
        s[0][j][0] = 1;

    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            d2[i][j] = max(d2[i - 1][j], d2[i][j - 1]);
            if (a[i] == b[j])
                d2[i][j] = max(d2[i][j], d2[i - 1][j - 1] + 1);
            vec[d2[i][j]].push_back({i, j});
        }
    int len = d2[n][m];
    for (i = 0; i <= len; i++)
    {
        for (pair <int, int> x : vec[i])
        {
            if (a[x.first] == b[x.second])
            {
                d[x.first][x.second] = sum(last[x.first][0], x.first - 1, last[x.second][1], x.second - 1, i - 1);
            }
            update(x.first, x.second, i);
        }
        if (i > 0)
        {
            for (pair <int, int> x : vec[i - 1])
                s[x.first][x.second][(i - 1) & 1] = 0;
            if (i == 1)
            {
                for (j = 0; j <= n; j++)
                    s[j][0][0] = 0;
                for (j = 0; j <= m; j++)
                    s[0][j][0] = 0;
            }
        }
    }
    int ans = 0;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            if (a[i] == b[j] and d2[i][j] == len)
                ans = (ans + d[i][j]) % MOD;
    cout << ans;
}