#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <climits>

using namespace std;

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

const int MAXN = 502;
const int MOD = 666013;

int dp[MAXN][MAXN], cnt[MAXN][MAXN];
string a, b;
int N, M;


int main()
{
    fin >> a >> b;
    N = a.size();
    M = b.size();
    a = " " + a;
    b = " " + b;

    for (int i = 0; i <= N; ++i) {
        cnt[i][0] = 1;
    }
    for (int i = 0; i <= M; ++i) {
        cnt[0][i] = 1;
    }

    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            if (a[i] == b[j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                cnt[i][j] = cnt[i - 1][j - 1];
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                dp[i][j] = dp[i - 1][j];
                cnt[i][j] = cnt[i - 1][j];
            } else if (dp[i][j - 1] > dp[i - 1][j]) {
                dp[i][j] = dp[i][j - 1];
                cnt[i][j] = cnt[i][j - 1];
            } else {
                dp[i][j] = dp[i - 1][j];
                cnt[i][j] = cnt[i - 1][j] + cnt[i][j - 1];
                // check if (i, j-1) and (i-1,j) both come from (i-1,j-1)
                if (dp[i - 1][j - 1] == dp[i][j]) {
                    cnt[i][j] -= cnt[i - 1][j - 1] - MOD;
                }
                while (cnt[i][j] >= MOD) cnt[i][j] -= MOD;
            }
        }
    }

    fout << cnt[N][M] << '\n';
    return 0;
}