#include <bits/stdc++.h>

using namespace std;

ifstream fin("subsir.in");
ofstream fout("subsir.out");
const int mod = 666013;
int n, m, i, j, d[502][502], rasp[502][502];
char a[502], b[502];

int main() {
    fin >> a >> b;
    n = strlen(a);
    m = strlen(b);
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            if(a[i - 1] == b[j - 1]) {
                d[i][j] = d[i - 1][j - 1] + 1;
                rasp[i][j] = max(1, rasp[i - 1][j - 1]);
            }
            else {
                if(d[i - 1][j] == d[i][j - 1]) {
                    d[i][j] = d[i - 1][j];
                    rasp[i][j] = (rasp[i - 1][j] + rasp[i][j - 1]) % mod;

                    if(d[i - 1][j] == d[i - 1][j - 1]) rasp[i][j] = (rasp[i][j] - rasp[i - 1][j - 1] + mod) % mod;
                }
                else if(d[i - 1][j] > d[i][j - 1]) {
                    d[i][j] = d[i - 1][j];
                    rasp[i][j] = rasp[i - 1][j];
                }
                else {
                    d[i][j] = d[i][j - 1];
                    rasp[i][j] = rasp[i][j - 1];
                }
            }
        }
    }

    fout << rasp[n][m];

    return 0;
}