#include <bits/stdc++.h>

using namespace std;
#define D 506
#define MOD 666013
char a[D],b[D];
int n,m,i,j;

int d[2][D],s[2][D];
bool k;

int main()
{
    freopen("subsir.in" , "r" , stdin);
    freopen("subsir.out","w", stdout);

    scanf("%s\n%s",a,b);
    n = strlen(a);
    m = strlen(b);
    while(true){
        s[0][i]=s[0][i+1]=s[0][i+2]=s[0][i+3]=s[0][i+4]=1;
        i+=5;
        if( i > m) break;
    }
    s[1][0]=1;
    for(i=1;i<=n;++i){
        for(j=1;j<=m;++j){
            if( a[i-1] == b[j-1] ){
                d[!k][j] = d[k][j-1]+1;
                s[!k][j] = s[k][j-1];
            }else if( d[k][j] > d[!k][j-1] ){
                d[!k][j] = d[k][j];
                s[!k][j] = s[k][j];
            }else if( d[k][j] < d[!k][j-1] ){
                d[!k][j] = d[!k][j-1];
                s[!k][j] = s[!k][j-1];
            }else{
                d[!k][j] = d[k][j];
                s[!k][j] =(s[k][j] + s[!k][j-1]) % MOD;
                if( d[k][j] == d[k][j-1] )
                    s[!k][j] = (s[!k][j] -s[k][j-1] + MOD) % MOD;

            }
            d[k][j-1]=0;
            s[k][j-1]=0;
        }
        d[k][m]=0;
        s[k][m]=0;
        s[k][0]=1;
        k = 1 - k;


    }
    printf("%d\n", s[k][m]);


    return 0;
}