#include <fstream>
#define MOD 666013

using namespace std;
ifstream fin ("subsir.in");
ofstream fout ("subsir.out");
int n, m, dp[505][505], nr;
char a[505], b[505];

int maxim (int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

int main()
{
    int i, j;
    fin >> a >> b;

    i = 0; j = 0;
    while (a[i++]) n++;
    while (b[j++]) m++;

    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            if (a[i-1] == b[j-1])
                dp[i][j] = 1+ dp[i-1][j-1];
            else
                dp[i][j] = maxim(dp[i-1][j], dp[i][j-1]);
        }
    }

    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            if (dp[i][j] == dp[n][m] && a[i-1] == b[i-1]) {
                nr++;
                nr %= MOD;
            }
        }
    }

    fout << nr;
    return 0;
}