#include <bits/stdc++.h>
#define MOD 666013

using namespace std;

char a[505],b[505];
int dp[505][505],cn[505][505];

int main() {
    ifstream fin("subsir.in");
    ofstream fout("subsir.out");
    int n,m;
    fin >> a + 1 >> b + 1;
    n = strlen(a + 1), m = strlen(b + 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;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    for (int i = 0;i <= m;i++)
        cn[0][i] = 1;
    for (int i = 0;i <= m;i++)
        cn[i][0] = 1;
    for (int i = 1;i <= n;i++) {
        for (int 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;
        }
    }
    fout << cn[n][m];
}