#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 = 1; i <= n; i++ ) nr[i][0] = 1;
    for( int i = 1; 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][j - 1] + nr[i - 1][j] ) % 666013;
                        if( nr[i - 1][j - 1] = nr[i][j - 1] ){
                            nr[i][j] = ( nr[i][j] - nr[i - 1][j - 1] + 666013 ) % 666013;
                        }
                    }
                }
            }
        }
    }
    fout << nr[n][m];
    return 0;
}