#include <fstream>
#include <cstring>

using namespace std;

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

const int N = 505, mod = 666013;
char a[N], b[N];
int n, m, i, j, dp[N][N], cn[N][N];

int main() {
    f >> a+1 >> b+1;
    n = strlen(a+1), m = strlen(b+1);
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++) {
            if (a[i] == b[j])
                dp[i][j] = dp[i-1][j-1]+1;
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }

    for (i = 0; i <= m; i++)
        cn[0][i] = 1;
    for (i = 0; i <= m; i++)
        cn[i][0] = 1;

    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            if (a[i] == b[j]) {
                cn[i][j] = cn[i-1][j-1];
                continue;
            }
            if (dp[i][j] == dp[i-1][j])
                cn[i][j] += cn[i-1][j];
            if (dp[i][j] == dp[i][j-1])
                cn[i][j] += cn[i][j-1];
            if(dp[i-1][j-1] == dp[i][j])
                cn[i][j] = cn[i][j] - cn[i-1][j-1] + mod;
            if (cn[i][j] >= mod) cn[i][j] -= mod;
        }
    }
    g << cn[n][m];
}