#include <stdio.h>
#include <string.h>
#include <fstream>

using namespace std;

const int N_MAX = 502, mod = 666013;
int n, m, d[N_MAX][N_MAX], rez[N_MAX][N_MAX];
char a[N_MAX], b[N_MAX];

void read ()
{
    ifstream f("subsir.in");
    f >> (a+1);
    f >> (b+1);
    a[0] = b[0] = 1;
    n = strlen(a) - 1;
    m = strlen(b) - 1;
    f.close();
}

void solve ()
{
    for (int i = 0; i <= max(n, m); i ++ )
        rez[i][0] = rez[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;
                rez[i][j] = rez[i-1][j-1];
            }
            else if ( d[i-1][j] > d[i][j-1] )
            {
                d[i][j] = d[i-1][j];
                rez[i][j] = rez[i-1][j];
            }
            else if ( d[i][j-1] > d[i-1][j] )
            {
                d[i][j] = d[i][j-1];
                rez[i][j] = rez[i][j-1];
            }
            else
            {
                d[i][j] = d[i-1][j];
                rez[i][j] = (rez[i][j-1] + rez[i-1][j]) % mod;
                if ( d[i][j] == d[i-1][j-1] )
                    rez[i][j] -= rez[i-1][j-1];
                if ( rez[i][j] < 0 )
                    rez[i][j] += mod;
            }
        }
}

void write ()
{
    ofstream g("subsir.out");
    g << rez[n][m] << "\n";
    g.close();
}

int main()
{
    read();
    solve();
    write();
    return 0;
}