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

ifstream f("subsir.in");
ofstream g("subsir.out");

int dp[501][501], mods[501][501];

int main() {
    string a, b;
    f >> a >> b;

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

    for (int i = 0; i <= m; i++) {
        mods[0][i] = 1;
    }
    for (int i = 0; i <= n; i++) {
        mods[i][0] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = (dp[i - 1][j - 1] + 1) % MOD;
                mods[i][j] = mods[i - 1][j - 1];
            } else {
                if (dp[i - 1][j] < dp[i][j - 1]) {
                    dp[i][j] = dp[i][j - 1];
                    mods[i][j] = mods[i][j - 1];
                } else if (dp[i - 1][j] > dp[i][j - 1]) {
                    dp[i][j] = dp[i - 1][j];
                    mods[i][j] = mods[i - 1][j];
                } else {
                    dp[i][j] = dp[i][j - 1];
                    mods[i][j] = (mods[i - 1][j] + mods[i][j - 1]) % MOD;
                    if (dp[i - 1][j - 1] == dp[i][j - 1]) {
                        mods[i][j] = (mods[i][j] - mods[i - 1][j - 1] + MOD) % MOD;
                    }
                }
            }
        }
    }

    g << mods[n][m];
}