#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();

    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] = max(cnt[i-1][j-1], 1);
            }
            else {
                len[i][j] = max(len[i][j-1], len[i-1][j]);
                if(len[i][j] == len[i-1][j])
                    cnt[i][j] = (cnt[i][j] + cnt[i-1][j]) % modulo;
                if(len[i][j] == len[i][j-1])
                    cnt[i][j] = (cnt[i][j] + cnt[i][j-1]) % modulo;
                if(len[i][j] == len[i-1][j-1] and len[i-1][j] == len[i][j-1])
                    cnt[i][j] = (cnt[i][j] - cnt[i-1][j-1] + modulo) % modulo;
            }
        }
    g << cnt[n][m];
    return 0;
}