#include <cstdio>
#include <cstring>
#define NMax 503
#define Type 256

const int MOD = 666013;

int posA[NMax+1][Type+1];
int posB[NMax+1][Type+1];
int lcs[NMax+1][NMax+1];
int nr[NMax+1][NMax+1];
int last[2][Type+1];
char A[NMax+1];
char B[NMax+1];

inline int MAX(int a,int b)
{
    if( a > b ) return a;
    return b;
}

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

    int ii,jj,i,j,z,N,M,ok,ans=0;

    fgets(A, NMax, stdin);
    fgets(B, NMax, stdin);
    N = strlen(A); if( A[N-1]=='\n' ) --N;
    M = strlen(B); if( B[M-1]=='\n' ) --M;

    for(i = N; i >= 1; --i) A[i] = A[i-1];
    for(i = M; i >= 1; --i) B[i] = B[i-1];

    for(i = N; i >= 1; --i)
        for(j = M; j >= 1; --j)
        if( A[i]==B[j] ) lcs[i][j] = 1 + lcs[i+1][j+1];
        else lcs[i][j] = MAX( lcs[i+1][j], lcs[i][j+1] );

    for(i = N; i >= 1; --i)
    {
        for(j = 'a'; j <= 'z'; ++j) posA[i][j] = last[0][j];
        last[0][ A[i] ] = i;
    }

    for(i = M; i >= 1; --i)
    {
        for(j = 'a'; j <= 'z'; ++j) posB[i][j] = last[1][j];
        last[1][ B[i] ] = i;
    }

    for(i = N; i >= 1; --i)
        for(j = M; j >= 1; --j)
        if( A[i]==B[j] )
        {
            for(ok = 0, z = 'a'; z <= 'z'; ++z)
            if( posA[i][z] && posB[j][z] )
            {
                ii = posA[i][z];
                jj = posB[j][z];
                if( lcs[i][j] == lcs[ii][jj] + 1 ) { nr[i][j] = ( nr[i][j] + nr[ii][jj] ) % MOD; ok = 1; }
            }
            if(!ok) nr[i][j] = 1;
        }

    for(i = 0; i <= 1; ++i)
        for(j = 'a'; j <= 'z'; ++j) last[i][j] = 0;

    for(i = 1; i <= N; ++i)
    if( !last[0][ A[i] ] ) last[0][ A[i] ] = i;

    for(i = 1; i <= M; ++i)
    if( !last[1][ B[i] ] ) last[1][ B[i] ] = i;

    for(i = 'a'; i <= 'z'; ++i)
    if( last[0][i] && last[1][i] )
        if( lcs[ last[0][i] ][ last[1][i] ] == lcs[1][1] )
        ans = ( ans + nr[ last[0][i] ][ last[1][i] ] ) % MOD;

    printf("%d\n",ans);



return 0;
}