//V[i][litera] indicele ultimei aparitii a literei inaintea pozitiei i in sirul a
//W[i][litera] indicele ultimei aparitii a literei inaintea pozitiei i in sirul b
#include <fstream>
#include <string.h>
#define DIM 510
#define MOD 666013
using namespace std;

char A[DIM];
char B[DIM];

int V[DIM][DIM], W[DIM][DIM], S[DIM][DIM], D[DIM][DIM];
//D[i][j] = lungimea maxima a unui subsir comun cu elemente dintre primele i din a
// si primele j din b
// S[i][j] = cate astfel de subsiruri de lungime D[i][j] exita
// updatez S[i][j] din pozitii pa,pb cu D[pa][pb] + 1 == D[i][j] si, pa,pb reprezinta,
// pentru fiecare litera poitia anterioara pe care ea apare in ambele siruri

int N, M, i, j, k, pa, pb;

int main() {
    ifstream f("subsir.in");
    ofstream g("subsir.out");
    f>>A+1;
    f>>B+1;
    N = strlen(A+1);
    M = strlen(B+1);
    A[++N] = 'z'+1;
    B[++M] = 'z'+1;

    for (k='a';k<='z';k++)
        for (i=1;i<=N;i++)
            if (A[i-1] == k)
                V[i][k] = i-1;
            else
                V[i][k] = V[i-1][k];

    for (k='a';k<='z';k++)
        for (i=1;i<=M;i++)
            if (B[i-1] == k)
                W[i][k] = i-1;
            else
                W[i][k] = W[i-1][k];

    S[0][0] = 1;
    for (i=1;i<=N;i++)
        for (j=1;j<=M;j++) {
            if (A[i] == B[j]) {
                D[i][j] = D[i-1][j-1] + 1;
            } else
                if (D[i-1][j] > D[i][j-1]) {
                    D[i][j] = D[i-1][j];
                } else {
                    D[i][j] = D[i][j-1];
                }
            if (D[i][j] == 1) {
                S[i][j] = 1;
                continue;
            }
            for (k = 'a';k<='z';k++) {
                pa = V[i][k];
                pb = W[j][k];
                if (D[i][j] == D[pa][pb] + 1) {
                    S[i][j] += S[pa][pb];
                    if (S[i][j] >= MOD)
                        S[i][j] -= MOD;
                }
            }
        }

    g<<S[N][M];
    return 0;
}