#include <bits/stdc++.h>

using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");
const int mod = 666013;
void add_self(int &a, int b) {
    a += b;
    if(a >= mod)
        a -= mod;
}

int main() {
	string A, B;
	fin >> A >> B;
	int N = A.size(), M = B.size();
	A = '0' + A, B = '0' + B;
	vector < vector < int > > dp(N + 1, vector < int >(M + 1)), cnt(N + 1, vector < int >(M + 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;
                if(cnt[i - 1][j - 1] == 0)
                    cnt[i][j] = 1;
                else
                    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];
                    add_self(cnt[i][j], cnt[i - 1][j]);
                }
            else
                if(dp[i - 1][j] < dp[i][j - 1]) {
                    dp[i][j] = dp[i][j - 1];
                    add_self(cnt[i][j], cnt[i][j - 1]);
                }
            else {
                dp[i][j] = dp[i - 1][j];
                add_self(cnt[i][j], cnt[i - 1][j]);
                add_self(cnt[i][j], cnt[i][j - 1]);
                if(dp[i][j - 1] == dp[i - 1][j - 1])
                    cnt[i][j] = (cnt[i][j] - cnt[i - 1][j - 1] + mod) % mod;
            }
        }
	fout << cnt[N][M];
}