#include <cstdio>
#include <cstring>

#define rint register int

const char IN[]="subsir.in";
const char OUT[]="subsir.out";
const int MAX = 514;
const int MOD = 666013;

using namespace std;

int d[MAX][MAX],nr[MAX][MAX];
char A[MAX],B[MAX];

int main()
{
    freopen( IN , "r" , stdin );
    freopen( OUT , "w" , stdout );
    gets(A+1);
    gets(B+1);
    int n=strlen(A+1);
    int m=strlen(B+1);
    for( rint i=0 ; i<=n ; ++i )nr[i][0]=1;
    for( rint i=0 ; i<=m ; ++i )nr[0][i]=1;
    for( rint i=1 ; i<=n ; ++i )
        for( rint j=1 ; j<=m ; ++j )
        if(A[i]==B[j]){
            d[i][j]=d[i-1][j-1]+1;
            nr[i][j]=nr[i-1][j-1];
        }
        else if(d[i-1][j]>d[i][j-1]){
            d[i][j]=d[i-1][j];
            nr[i][j]=nr[i-1][j];
        }
        else if(d[i-1][j]<d[i][j-1]){
            d[i][j]=d[i][j-1];
            nr[i][j]=nr[i][j-1];
        }
        else {
            d[i][j]=d[i-1][j];
            nr[i][j]=(nr[i][j-1]+nr[i-1][j])%MOD;
            if(d[i-1][j-1]==d[i-1][j])nr[i][j]=(nr[i][j]-nr[i-1][j-1]+MOD)%MOD;
        }
    printf("%d\n",nr[n][m]);
    return 0;
}