#include <bits/stdc++.h>
#include <fstream>
#define MOD 666013
using namespace std;
int n, m, dp[505][505], nr[505][505];
char a[505], b[505];

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

    fout << nr[n][m] << '\n';
    fin.close();
    fout.close();
    return 0;
}