#include <bits/stdc++.h>

const int MAXN = (int) 502;
const int MOD = (int) 666013;
const int SIGMA = (int) 26;

int len[MAXN + 1][MAXN + 1];
int dp[MAXN + 1][MAXN + 1];

char a[MAXN + 1], b[MAXN + 1];

int nxta[SIGMA][MAXN + 1], nxtb[SIGMA][MAXN + 1];

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

int main() {
    FILE *fi, *fout;
    int i, j, n, m;
    char ch;
    fi = fopen("subsir.in" ,"r");
    fout = fopen("subsir.out" ,"w");
    fscanf(fi,"%s %s " , a + 1, b + 1);
    n = strlen(a + 1);
    m = strlen(b + 1);
    a[++n] = 'z';
    b[++m] = 'z';
    a[0] = b[0] = -1;
    for(i = 1; i <= n; i++) {
        a[i] -= 'a';
        for(ch = 0; ch < SIGMA; ch++) {
            if(a[i - 1] == ch)
                nxta[ch][i] = i - 1;
            else
                nxta[ch][i] = nxta[ch][i - 1];
        }
    }
    for(i = 1; i <= m; i++) {
        b[i] -= 'a';
        for(ch = 0; ch < SIGMA; ch++) {
            if(b[i - 1] == ch)
                nxtb[ch][i] = i - 1;
            else
                nxtb[ch][i] = nxtb[ch][i - 1];
        }
    }
    int maxlen = 0;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++) {
            if(a[i] == b[j]) {
                 for(ch = 0; ch < SIGMA; ch++)
                    len[i][j] = std::max(len[i][j], len[nxta[ch][i]][nxtb[ch][j]] + 1);
                 for(ch = 0; ch < SIGMA; ch++)
                    if(len[i][j] == len[nxta[ch][i]][nxtb[ch][j]] + 1) {
                          dp[i][j] += dp[nxta[ch][i]][nxtb[ch][j]];
                          mod(dp[i][j]);
                    }
                 if(len[i][j] == 1)
                    dp[i][j] = 1;
                 maxlen = std::max(len[i][j], maxlen);
            }
        }
    fprintf(fout,"%d" ,dp[n][m]);
    fclose(fi);
    fclose(fout);
    return 0;
}