#include <bits/stdc++.h>
#define MOD 666013


using namespace std ;

const int NMAX = 505 ;



ifstream fin("subsir.in") ;
ofstream fout("subsir.out");

char A[NMAX], B[NMAX] ;
int N, M, D[NMAX][NMAX], NR[NMAX][NMAX];

int main()
{
    fin >> A + 1>> 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])
                {
                    D[i][j] = D[i - 1][j - 1]  + 1 ;
                    NR[i][j] = NR[i - 1][j - 1] ;
                }
                else if(D[i - 1][j] == D[i][j  - 1])
                {
                    D[i][j] = D[i - 1][j] ;
                    NR[i][j] = (NR[i][j - 1] + NR[i - 1][j]) % MOD ;
                    if(D[i][j - 1] == D[i - 1][j - 1])
                    {
                        NR[i][j] -= NR[i - 1][j - 1] ;
                        NR[i][j] %= MOD ;

                    }
                }
                else    if(D[i][j - 1] > D[i - 1][j])
                    {
                        D[i][j] = D[i][j - 1] ;
                        NR[i][j] = NR[i][j - 1] ;

                }
                 else    if(D[i][j - 1] < D[i - 1][j])
                    {
                        D[i][j] = D[i - 1][j] ;
                        NR[i][j] = NR[i - 1][j ] ;

                }

    if(NR[N][M] < 0 )
        NR[N][M] += MOD ;


    fout << NR[N][M] << '\n' ;




    fin.close() ;
    fout.close() ;
    return  0 ;
}