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

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


signed main()
{
    ifstream cin("subsir.in");
    ofstream cout("subsir.out");
    int i, j, k, l, n, m;
    string a, b;
    cin >> a >> b;
    n = a.size();
    m = b.size();
    a = "!" + a;//scuze Francu
    b = "!" + b;

    d[1][1][0] = 1;
    int len = 0;
    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 >= 1 and a[l1] != a[i]; l1--)
                        for (int l2 = j - 1; l2 >= 1 and b[l2] != b[j]; l2--)
                            d[i][j][k] = (d[i][j][k] + d[l1][l2][k - 1]) % MOD;
                    if (d[i][j][k])
                        len = k;
                }
    int ans = 0;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            if (a[i] == b[j])
                ans = (ans + d[i][j][len]) % MOD;
    cout << ans;
}