//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

//d[i][j][k] = daca a[i] == b[j],
//

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

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

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]


void add_self(int &a, int b)
{
    a += b;
    if (a > MOD)
        a -= MOD;
}

void sub_self(int &a, int b)
{
    a -= b;
    if (a < 0)
        a += MOD;
}

void calc(int k, int n, int m)
{
    int i, j;
    for (i = 0; i <= n; i++)
        for (j = 0; j <= m; j++)
        {
            s[i][j][k] = d[i][j][k];
            if (i - 1 >= 0)
                add_self(s[i][j][k], s[i - 1][j][k]);
            if (j - 1 >= 0)
                add_self(s[i][j][k], s[i][j - 1][k]);
            if (i - 1 >= 0 and j - 1 >= 0)
                sub_self(s[i][j][k], s[i - 1][j - 1][k]);
        }
}

int sum(int i1, int i2, int j1, int j2, int k)
{
    int ans = s[i2][j2][k];
    if (i1 - 1 >= 0 and j1 - 1 >= 0)
        add_self(ans, s[i1 - 1][j1 - 1][k]);
    if (j1 - 1 >= 0)
        sub_self(ans, s[i2][j1 - 1][k]);
    if (i1 - 1 >= 0)
        sub_self(ans, s[i1 - 1][j2][k]);
    return ans;
}
signed main()
{
    ifstream cin("subsir.in");
    ofstream cout("subsir.out");
    int i, j, k, 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;
    }
    int len = 0;

    d[0][0][0] = 1;
    calc(0, n, m);
    for (k = 1; k <= n and k <= m; k++)
    {
        for (j = 1; j <= m; j++)
            for (i = 1; i <= n; i++)
                if (a[i] == b[j])
                {
                    /*for (int l1 = i - 1; l1 >= last[i][0]; l1--)
                        for (int l2 = j - 1; l2 >= last[j][1]; l2--)
                            d[i][j][k] = (d[i][j][k] + d[l1][l2][k - 1]) % MOD;*/
                    add_self(d[i][j][k], sum(last[i][0], i - 1, last[j][1], j - 1, k - 1));
                    if (d[i][j][k])
                        len = k;
                }
        calc(k, n, m);
    }
    int ans = 0;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            if (a[i] == b[j])
                add_self(ans, d[i][j][len]);
    cout << ans;
}