#include <bits/stdc++.h>
using namespace std;
const int nmax = 500;
const int modulo = 666013;

int len[nmax+5][nmax+5];
int cnt[nmax+5][nmax+5];

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

    string a, b; f >> a >> b;

    a = " " + a; b = " " + b;
    int n = a.size(), m = b.size();

    cnt[0][0] = 1;
    cnt[0][1] = 1;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) {
            if(a[i] == b[j]) {
                len[i][j] = len[i-1][j-1] + 1;
                cnt[i][j] = cnt[i-1][j-1];
            }
            else if(len[i-1][j] > len[i][j-1]) {
                len[i][j] = len[i-1][j];
                cnt[i][j] = cnt[i-1][j];
            }
            else if(len[i][j-1] > len[i-1][j]) {
                len[i][j] = len[i][j-1];
                cnt[i][j] = cnt[i][j-1];
            }
            else {
                len[i][j] = len[i][j-1];
                cnt[i][j] = (cnt[i-1][j] + cnt[i][j-1]) % modulo;
            }
        }
    g << cnt[n][m];
    return 0;
}