#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
const int Nmax = 505, mod = 666013;
string y, x, a = "1", b = "2";
int d[Nmax][Nmax], nr[Nmax][Nmax], n, m;
int main()
{
    freopen("subsir.in", "r", stdin);
    freopen("subsir.out", "w", stdout);
    getline(cin, x);
    getline(cin, y);
    a += x;
    b += y;
    m = x.size() + 1, n = y.size() + 1;
    for (int i = 0; i <= max(m, n); ++i)
        nr[0][i] = nr[i][0] = 1;
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            if (a[i] == b[j])
            {
                d[i][j] = d[i-1][j-1] + 1;
                nr[i][j] = nr[i-1][j-1];
            }
            else
                if (d[i][j-1] == d[i-1][j])
                {
                    d[i][j] = d[i][j-1];
                    nr[i][j] = (nr[i][j-1] + nr[i-1][j]) % mod;
                    if (d[i][j] == d[i-1][j-1])
                        nr[i][j] = (nr[i][j] - nr[i-1][j-1] + mod) % mod;
                }
            else
                if (d[i][j-1] > d[i-1][j])
                {
                    d[i][j] = d[i][j-1];
                    nr[i][j] = nr[i][j-1];
                }
            else
                if (d[i-1][j] > d[i][j-1])
                {
                    d[i][j] = d[i-1][j];
                    nr[i][j] = nr[i-1][j];
                }
    cout<<nr[m][n];
    return 0;
}