#include <fstream>
#include <string>
using namespace std;

ifstream f("subsir.in"); ofstream g("subsir.out");

const int NMAX = 505;
const int M = 666013;
string A, B;

int Count[NMAX][NMAX], DP[NMAX][NMAX] ;

inline void init(int n, int m) {
    for(int i = 0; i <= n; ++i) Count[i][0] = 1;

    for(int j = 0; j <= m; ++j) Count[0][j] = 1;
}

int main() {
    f >> A >> B;

    int n = A.length();
    int m = B.length();

    init(n, m);

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

            if(A[i - 1] == B[j - 1])
                DP[i][j] = DP[i - 1][j - 1] + 1,
                Count[i][j] = Count[i - 1][j - 1];
            else

            if(DP[i - 1][j] == DP[i][j - 1]){
                DP[i][j] = DP[i - 1][j],
                Count[i][j] = (Count[i - 1][j]  + Count[i][j - 1]) % M;
                if(DP[i][j - 1] == DP[i - 1][j - 1])
                    Count[i][j] = (Count[i][j] - Count[i - 1][j - 1] + M) % M;
            }
            else

            if(DP[i - 1][j] > DP[i][j - 1])
                DP[i][j] = DP[i - 1][j],
                Count[i][j] = Count[i - 1][j];
            else

                DP[i][j] = DP[i][j - 1],
                Count[i][j] = Count[i][j - 1];
        }

    g << Count[n][m] << '\n';

    g.close();
    return 0;
}