#include <iostream>
#include <stdio.h>
using namespace std;
const int N=505;
const int MOD=666013;
long long drum[N][N],n,m,l[N][N];
char a[N],b[N],v[N];

inline int  maxim(int x, int y){ if(x>y) return x; return y;}

void citire(){
    FILE * in;
    in=fopen("subsir.in","r");
    fgets(a,504, in);
    while(a[n]!=NULL) n++;
    n--;
    fgets(b,504, in);
    while(b[m]!=NULL) m++;
    m--;
}

 void rez(){

    l[0][0]=1;
    for(int i=1;i<=n;i++)l[i][0]=1;
    for(int i=1;i<=m;i++)l[0][i]=1;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i-1]==b[j-1]){
                drum[i][j]=1+drum[i-1][j-1];
                l[i][j]=l[i-1][j-1];
            }
            else if(drum[i-1][j]==drum[i][j-1]){
                drum[i][j]=drum[i-1][j];
                l[i][j]=(l[i-1][j]+l[i][j-1])%MOD;
                if(drum[i-1][j]==drum[i-1][j-1]) l[i][j]=(l[i][j]-l[i-1][j-1]+MOD)%MOD;
            }
                else if(drum[i-1][j]<drum[i][j-1]){
                    drum[i][j]=drum[i][j-1];
                    l[i][j]=l[i][j-1];
                }
                    else if(drum[i-1][j]>drum[i][j-1]){
                        drum[i][j]=drum[i-1][j];
                        l[i][j]=l[i-1][j];
                        }
 }

void afisare(){
    FILE *out;
    out=fopen("subsir.out","w");

        fprintf(out,"%lld",l[n][m]);

}

int main()
{
    citire();
    rez();
    afisare();
    return 0;
}