#include <iostream>
#include <fstream>

using namespace std;
ifstream f("subsir.in");
ofstream g("subsir.out");
const int NMAX = 501, MOD = 666013;
int lg[NMAX][NMAX], nrSiruri[NMAX][NMAX]; /// va fi indexata de la 1

int main()
{
    string a, b;
    f >> a >> b;
    int n = a.size(), m = b.size();
    for (int i = 0; i <= n; i++)
    {
        nrSiruri[i][0] = 1;
    }
    for (int i = 0; i <= m; i++)
    {
        nrSiruri[0][i] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i - 1] == b[j - 1])
            {
                nrSiruri[i][j] = nrSiruri[i - 1][j - 1];
                lg[i][j] = lg[i - 1][j - 1] + 1;
            }
            else
            {
                if (lg[i - 1][j] > lg[i][j - 1])
                {
                    lg[i][j] = lg[i - 1][j];
                    nrSiruri[i][j] = nrSiruri[i - 1][j];
                }
                else if (lg[i - 1][j] < lg[i][j - 1])
                {
                    lg[i][j] = lg[i][j - 1];
                    nrSiruri[i][j] = nrSiruri[i][j - 1];
                }
                else /// sunt egale
                {
                    lg[i][j] = lg[i][j - 1];
                    nrSiruri[i][j] = (nrSiruri[i - 1][j] + nrSiruri[i][j - 1]) % MOD;
                    if (lg[i - 1][j - 1] == lg[i][j - 1])
                    {
                        nrSiruri[i][j] = (nrSiruri[i][j] - nrSiruri[i - 1][j - 1] + MOD) % MOD;
                    }
                }
            }
        }
    }
    g << nrSiruri[n][m];
    return 0;
}