#include<stdio.h>
#include<string.h>
#define NMAX 512
#define MOD 666013
 
int N, M, i, j, D[NMAX][NMAX], Nr[NMAX][NMAX];
char A[NMAX], B[NMAX];
 
int main()
{
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
 
    scanf("%s\n", A+1); N = strlen(A+1);
    scanf("%s\n", B+1); M = strlen(B+1);
 
    for( i=0; i<=N; i++ ) Nr[i][0] = 1;
    for( j=0; j<=M; j++ ) Nr[0][j] = 1;
 
    for( i=1; i<=N; i++ )
        for( 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] + Nr[i][j-1] ) % MOD;
 
                if( D[i-1][j] == D[i-1][j-1] )
                    Nr[i][j] = ( Nr[i][j] - Nr[i-1][j-1] + MOD ) % MOD;
            }
            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][j-1] > D[i-1][j] )
            {
                D[i][j] = D[i][j-1];
                Nr[i][j] = Nr[i][j-1];
            }
        }
 
    printf("%d\n", Nr[N][M]);              
 
    return 0;
}