#include <bits/stdc++.h>

using namespace std;
ifstream in("subsir.in");
ofstream out("subsir.out");

const int NMAX = 1030;
const int MOD = 666013;

int dp[NMAX][NMAX], nr[NMAX][NMAX];
string a, b;

int main() {

    in >> a >> b;
    a = " " + a;
    b = " " + b;
    int n = a.size(), m = b.size();
    n --;
    m --;
    for(int i = 0; i <= n; i ++)
        nr[i][0] = 1;
    for(int j = 0; j <= m; j ++)
        nr[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;
                nr[i][j] = nr[i - 1][j - 1];
            } else if(dp[i - 1][j] > dp[i][j - 1]) {
                dp[i][j] = dp[i - 1][j];
                nr[i][j] = nr[i - 1][j];
            } else if(dp[i][j - 1] > dp[i - 1][j]) {
                dp[i][j] = dp[i][j - 1];
                nr[i][j] = nr[i][j - 1];
            } else {
                dp[i][j] = dp[i][j - 1];
                nr[i][j] = (nr[i][j - 1] + nr[i - 1][j]) % MOD;
                if(dp[i - 1][j - 1] == dp[i][j - 1])
                    nr[i][j] = (MOD + nr[i][j] - nr[i - 1][j - 1]) % MOD;
            }
        }
    }
    out << nr[n][m];
    return 0;
}