#include <fstream>
#include <cstring>
#define DIM 505
#define MOD 666013

using namespace std;

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

int N,M,P[DIM][DIM],D[DIM][DIM];
char a[DIM],b[DIM];
int main(){
    fin>>a+1>>b+1;
    N=strlen(a+1);
    M=strlen(b+1);
    for(int i=0;i<=N;i++)
        P[i][0]=1;
    for(int i=0;i<=M;i++)
        P[0][i]=1;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++){
            if(a[i]==b[j]){
                D[i][j]=D[i-1][j-1]+1;
                P[i][j]=P[i-1][j-1];
            }
            else{
                if(D[i-1][j]==D[i][j-1]){
                    D[i][j]=D[i-1][j];
                    P[i][j]=(P[i-1][j]+P[i][j-1])%MOD;
                    if(D[i][j]==D[i-1][j-1]){
                        P[i][j]=(P[i][j]-P[i-1][j-1])%MOD;
                    }
                }
                else{
                    if(D[i-1][j]>D[i][j-1]){
                        D[i][j]=D[i-1][j];
                        P[i][j]=P[i-1][j];
                    }
                    else{
                        D[i][j]=D[i][j-1];
                        P[i][j]=P[i][j-1];
                    }
                }
            }
        }
    fout<<P[N][M]%MOD<<"\n";
    fin.close();fout.close();
    return 0;
}