#include <fstream>
#include <cstring>
#define MOD 666013
#define DIM 502
using namespace std;
int n,m,i,j,k,sol,ii,jj,d[DIM][DIM],nr[DIM][DIM],c1[200][DIM],c2[200][DIM];
char a[DIM],b[DIM];
int main (){

    ifstream fin ("subsir.in");
    ofstream fout ("subsir.out");

    fin>>a+1;
    fin>>b+1;
    n = strlen (a+1);
    m = strlen (b+1);
    /// d[i][j] - lungimea maxima a unui subsir comun format cu primele i caractere din a si primele j caractere din b
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            if (a[i] == b[j])
                d[i][j] = 1 + d[i-1][j-1];
            else
                d[i][j] = max (d[i][j-1],d[i-1][j]);
    /// calculam pozitita ultimei aparitii a caracterului k pana la poz i in sirul a, respectiv b
    for (i='a';i<='z';i++){
        for (j=1;j<=n;j++){
            if (a[j] ==  i)
                c1[i][j] = j;
            else
                c1[i][j] = c1[i][j-1];
        }
        for (j=1;j<=m;j++)
            if (b[j] == i)
                c2[i][j] = j;
            else
                c2[i][j] = c2[i][j-1];
    }
    /// nr[i][j] - nr maxim de subsiruri de lungime maxima
    for (i=1;i<=n;i++){
        for (j=1;j<=m;j++){
            if (a[i] == b[j]){
                for (k='a';k<='z';k++){
                    if (a[i] == k){ /// daca ultimul caracter este egal cu k
                        ii = c1[k][i-1];
                        jj = c2[k][j-1];
                        if (d[i][j] == d[ii][jj] + 1){
                            nr[i][j] += nr[ii][jj];
                            if (nr[i][j] >= MOD)
                                nr[i][j] -= MOD;
                        }
                    }
                    else{
                        ii = c1[k][i];
                        jj = c2[k][j];
                        if (d[i][j] == d[ii][jj]+1){
                            nr[i][j] += nr[ii][jj];
                            if (nr[i][j] >= MOD)
                                nr[i][j] -= MOD;
                        }
                    }
                }
                if (nr[i][j] == 0)
                    nr[i][j] = 1; /// trebuie sa punem 1 daca nr[i][j] e 0 si a[i]==b[j]
            }
        }
    }
    for (i='a';i<='z';i++)
        if (d[c1[i][n]][c2[i][m]] == d[n][m]){
            sol += nr[c1[i][n]][c2[i][m]];
            if (sol > MOD)
                sol -= MOD;
        }
    fout<<sol;

    return 0;
}