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

const int MAX_N = 502;
const int MOD = 666013;

int N, M;
int D[MAX_N][MAX_N], Cnt[MAX_N][MAX_N];
char a[MAX_N], b[MAX_N];

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

    a[0] = b[0] = ' ';

    f >> (a + 1);
    f >> (b + 1);

    N = strlen(a), M = strlen(b);

    for(int i = 0; i < MAX_N; ++i)
        Cnt[i][0] = Cnt[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;
                Cnt[i][j] = Cnt[i - 1][j - 1];
            }
            else {
                if(D[i - 1][j] > D[i][j - 1]) {
                    D[i][j] = D[i - 1][j];
                    Cnt[i][j] = Cnt[i - 1][j];
                }
                else if(D[i - 1][j] < D[i][j - 1]) {
                    D[i][j] = D[i][j - 1];
                    Cnt[i][j] = Cnt[i][j - 1];
                }
                else {
                    D[i][j] = D[i - 1][j];
                    Cnt[i][j] = (Cnt[i - 1][j] + Cnt[i][j - 1]) % MOD;
                    if(D[i][j] == D[i - 1][j - 1])
                        Cnt[i][j] -= Cnt[i - 1][j - 1];
                    if(Cnt[i][j] < 0)
                        Cnt[i][j] += MOD;
                }
            }

    g << Cnt[N - 1][M - 1] << "\n";

    f.close();
    g.close();

    return 0;
}