#include <bits/stdc++.h>
#define DIM 510
#define mod 666013
using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");
int n,m,i,j,d[DIM][DIM],nr[DIM][DIM];
char A[DIM],B[DIM];
int main() {
    fin>>A>>B;
    n=strlen(A);
    m=strlen(B);
    //d[i][j]=lungimea celui mai lung subsir comun dintre sirurile A[1..i] si B[1..j]
    //nr[i][j]=numarul de subsiruri comune cu lungimea maxima dintre sirurile A[1..i] si B[1..j]
    //initializam cu 1 matricea pe "margini", intrucat daca avem un indice 0 avem un subsir de lungime maxima
    for (i=1;i<=n;i++)
        nr[i][0]=1;
    for (i=1;i<=m;i++)
        nr[0][i]=1;
    for (i=1;i<=n;i++) {
        for (j=1;j<=m;j++) {
            if (A[i]==B[j]) { //daca gasim litere egale, luam nr de pe pozitia anterioara, intrucat suntem pe drumul cu sirul maxim
                d[i][j]=1+d[i-1][j-1];
                nr[i][j]=nr[i-1][j-1];
            }
            else {
                d[i][j]=max(d[i-1][j],d[i][j-1]);
                if (d[i-1][j]==d[i][j-1]) { //daca vecinii sunt egali, atunci determina 2 subsiruri, deci adunam nr
                    nr[i][j]=(nr[i-1][j]+nr[i][j-1])%mod;
                    if (d[i-1][j]==d[i-1][j-1]) //dar daca si nr de pe pozitia anterioara este egala cu vecinii, trebuie sa scadem
                        nr[i][j]=(nr[i][j]-nr[i-1][j]+mod)%mod; //intrucat cele 2 subsiruri sunt identice
                }
                else { //in celelalte cazuri, alegem subsirul cu lungimea maxima
                    if (d[i-1][j]>d[i][j-1])
                        nr[i][j]=nr[i-1][j];
                    else
                        nr[i][j]=nr[i][j-1];
                }
            }
        }
    }
    fout<<nr[n][m];
    return 0;
}