#include <fstream>
#include <algorithm>
#include <climits>
#include <cstring>
#define ll long long
using namespace std;

//nu merge dinamica clasica, dar cu in loc de max, plus?
const int MOD = 666013;
const int NMAX = 500;

int d[NMAX + 1][NMAX + 1];
int len[NMAX + 1][NMAX + 1];
char a[NMAX + 1], b[NMAX + 1];

int pwr(int a, int b)
{
    int ans = 1;
    while (b)
    {
        if (b & 1)
            ans = 1LL * ans * a % MOD;
        a = 1LL * a * a % MOD;
        b >>= 1;
    }
    return ans;
}
int main()
{
    ifstream cin("subsir.in");
    ofstream cout("subsir.out");
    int i, j;
    cin >> (a + 1) >> (b + 1);
    int n1 = strlen(a + 1);
    int n2 = strlen(b + 1);
    d[0][0] = d[0][1] = d[1][0] = 1;
    for (i = 1; i <= n1; i++)
        for (j = 1; j <= n2; j++)
        {
            if (a[i] == b[j])
                len[i][j] = 1 + len[i - 1][j - 1];
            len[i][j] = max(len[i][j], max(len[i][j - 1], len[i - 1][j]));

            if (len[i][j] == 1 + len[i - 1][j - 1] and a[i] == b[j])
                d[i][j] = (d[i][j] + d[i - 1][j - 1]) % MOD;
            if (len[i][j] == len[i][j - 1])
                d[i][j] = (d[i][j] + d[i][j - 1]) % MOD;
            if (len[i][j] == len[i - 1][j])
                d[i][j] = (d[i][j] + d[i - 1][j]) % MOD;
        }
    cout << 1LL * d[n1][n2] * pwr(8, MOD - 2) % MOD;
}