#include <fstream>
#include <vector>
#include <string>
using namespace std;

const int MOD = 666013;
const int MAXN = 505;

int dp[MAXN][MAXN];
int cnt[MAXN][MAXN];

int main() {
    ifstream fin("zaharel.in");
    ofstream fout("zaharel.out");

    string a, b;
    fin >> a >> b;

    int n = a.size();
    int m = b.size();

    a = " " + a; // 1-based indexing
    b = " " + b;

    for (int i = 0; i <= n; ++i) cnt[i][0] = 1;
    for (int j = 0; j <= m; ++j) cnt[0][j] = 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 {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                cnt[i][j] = 0;

                if (dp[i-1][j] == dp[i][j])
                    cnt[i][j] = (cnt[i][j] + cnt[i-1][j]) % MOD;

                if (dp[i][j-1] == dp[i][j])
                    cnt[i][j] = (cnt[i][j] + cnt[i][j-1]) % MOD;

                if (dp[i-1][j-1] == dp[i][j])
                    cnt[i][j] = (cnt[i][j] - cnt[i-1][j-1] + MOD) % MOD;
            }
        }
    }

    fout << cnt[n][m] % MOD << '\n';
    return 0;
}