#include <algorithm>
using namespace std;

#define ALF 26
#define DIM 1<<9
#define MOD 666013

char a[ DIM ], b[ DIM ];
int N, M, XXX;
int lsc[ DIM ][ DIM ], sol[ DIM ][ DIM ], uaa[ ALF ][ DIM ], uab[ ALF ][ DIM ];

inline int max( const int &x, const int &y ) {

    if( x > y )
        return x;

    return y;
}

void calc_lsc() {

    int i, j;

    for( i = 1; i <= N; ++i )
        for( j = 1; j <= M; ++j )
            if( a[ i ] == b[ j ] )
                lsc[ i ][ j ] = lsc[ i-1 ][ j-1 ] + 1;
            else
                lsc[ i ][ j ] = max( lsc[ i-1 ][ j ], lsc[ i ][ j-1 ] );
}

void calc_uaa() {

    char ch;
    int i;

    for( ch = 'a'; ch < ALF + 'a'; ++ch )
        for( i = 1; i <= N; ++i ) {

            uaa[ ch - 'a' ][ i ] = uaa[ ch - 'a'][ i-1 ];
            if( a[ i ] == ch )
                uaa[ ch - 'a' ][ i ] = i;
        }
}

void calc_uab() {

    char ch;
    int i;

    for( ch = 'a'; ch < ALF + 'a'; ++ch )
        for( i = 1; i <= M; ++i ) {

            uab[ ch - 'a' ][ i ] = uab[ ch - 'a'][ i-1 ];
            if( b[ i ] == ch )
                uab[ ch - 'a' ][ i ] = i;
        }
}

void calc_sol() {

    char ch;
    int i, j, ii, jj;

    for( i = 1; i <= N; ++i )
        for( j = 1; j <= M; ++j )
            if( a[ i ] == b[ j ] )
                if( a[ i ] == b[ j ] && lsc[ i ][ j ] == 1 )
                    sol[ i ][ j ] = 1;
                else
                    for( ch = 'a'; ch < ALF + 'a'; ++ch ) {

                        ii = uaa[ ch - 'a' ][ i-1 ];
                        jj = uab[ ch - 'a' ][ j-1 ];
                        if( lsc[ ii ][ jj ] + 1 == lsc[ i ][ j ] )
                            sol[ i ][ j ] = ( sol[ i ][ j ] + sol[ ii ][ jj ] ) % MOD;
                    }
}

int main() {

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

    char ch;
    int i, j;

    gets( a+1 );
    N = strlen( a+1 );
    gets( b+1 );
    M = strlen( b+1 );

    calc_lsc();

//    for( int i = 1; i <= N; ++i ) {
//
//        for( int j = 1; j <= M; ++j )
//            printf( "%d ", lsc[ i ][ j ] );
//        printf( "\n" );
//    }

    calc_uaa();

//    for( int i = 0; i < ALF; ++i ) {
//
//        printf( "%c: ", i + 'a' );
//        for( int j = 1; j <= N; ++j )
//            printf( "%d ", uaa[ i ][ j ] );
//        printf( "\n" );
//    }

    calc_uab();

//    for( int i = 0; i < ALF; ++i ) {
//
//        printf( "%c: ", i + 'a' );
//        for( int j = 1; j <= M; ++j )
//            printf( "%d ", uab[ i ][ j ] );
//        printf( "\n" );
//    }

    calc_sol();

//    for( int i = 1; i <= N; ++i ) {
//
//        for( int j = 1; j <= M; ++j )
//            printf( "%d ", sol[ i ][ j ] );
//        printf( "\n" );
//    }

    for( i = 1; i <= N; ++i )
        for( j = 1; j <= M; ++j )
            if( sol[ i ][ j ] && lsc[ i ][ j ] == lsc[ N ][ M ] ) {

                ch = a[ i ];
                if( uaa[ ch - 'a' ][ N ] == i && uab[ ch - 'a' ][ M ] == j )
                    XXX = ( XXX + sol[ i ][ j ] ) % MOD;
            }

    printf( "%d", XXX );

    return 0;
}