#include <bits/stdc++.h>
using namespace std;

ifstream fin("subsir.in");
ofstream fout("subsir.out");

int a[501][501], r[501][501];
const int mod = 666013;
char x[505], y[505];

int main()
{
    fin >> (x + 1) >> (y + 1);

    int lgx = strlen(x + 1), lgy = strlen(y + 1);

    for (int i = 1; i <= lgx; i++)
        for (int j = 1; j <= lgy; j++)
            if (x[i] == y[j])
                a[i][j] = a[i - 1][j - 1] + 1;
            else
                a[i][j] = max(a[i - 1][j], a[i][j + 1]);

    r[lgx][lgy] = 1;

    for (int i = lgx; i >= 1; i--)
        for (int j = lgy; j >= 1; j--)
            if (x[i] == y[j])
            {
                r[i - 1][j - 1] += r[i][j];
                if (r[i - 1][j - 1] >= mod)
                    r[i - 1][j - 1] -= mod;
            }
            else
            {
                if (a[i - 1][j] == a[i][j])
                {
                    r[i - 1][j] += r[i][j];
                    if (r[i - 1][j] >= mod)
                        r[i - 1][j] -= mod;
                }

                if (a[i][j - 1] == a[i][j])
                {
                    r[i][j - 1] += r[i][j];
                    if (r[i][j - 1] >= mod)
                        r[i][j - 1] -= mod;
                }
            }

    fout << r[1][1];

    return 0;
}