#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");
int n, m;
int lg[505][505], nr[505][505];
char a[505], b[505];
int main(){

    fin >> a + 1;
    fin >> b + 1;
    n = strlen( a + 1 );
    m = strlen( b + 1 );

    for( int i = 0; i <= n; i++ ) nr[i][0] = 1;
    for( int i = 0; i <= m; i++ ) nr[0][i] = 1;

    for( int i = 1; i <= n; i++ ){

        for( int j = 1; j <= m; j++ ){

            if( a[i] == b[j] ){

                lg[i][j] = lg[i - 1][j - 1] + 1;
                nr[i][j] = nr[i - 1][j - 1];

            }else{

                if( lg[i - 1][j] > lg[i][j - 1] ){

                    lg[i][j] = lg[i - 1][j];
                    nr[i][j] = nr[i - 1][j];

                }else{

                    if( lg[i - 1][j] < lg[i][j - 1] ){

                        lg[i][j] = lg[i][j - 1];
                        nr[i][j] = nr[i][j - 1];

                    }else{

                        lg[i][j] = lg[i][j - 1];
                        nr[i][j] = ( nr[i - 1][j] + nr[i][j - 1] ) % 666013;
                        if( lg[i - 1][j - 1] == lg[i][j - 1] ){
                            nr[i][j] = ( nr[i][j] - nr[i - 1][j - 1] + 666013 ) % 666013;
                        }

                    }

                }

            }

        }

    }
    fout << nr[n][m];
    return 0;
}