#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("subsir.in");
ofstream g("subsir.out");
const int NMAX = 501, MOD = 666013;
short c[NMAX][NMAX];
char s1[NMAX], s2[NMAX];
int lg1, lg2;
int nr[NMAX][NMAX];
void calcul()
{
    for(int i = 0; i <= lg1; i++)
        nr[i][0] = 1;
    for(int i = 0; i <= lg2; i++)
        nr[0][i] = 1;
    for(int i = 1; i <= lg1; i++)
        for(int j = 1; j <= lg2; j++)
            if(s1[i - 1] == s2[j - 1])
            {
                c[i][j] = c[i - 1][j - 1] + 1;
                nr[i][j] = nr[i - 1][j - 1];
            }
            else
            {
                c[i][j] = max(c[i - 1][j], c[i][j - 1]);
                if(c[i - 1][j] == c[i][j - 1])
                {
                    nr[i][j] = (nr[i - 1][j] + nr[i][j - 1]) % MOD;
                    if(c[i - 1][j] == c[i - 1][j - 1])
                        nr[i][j] = (nr[i][j] - nr[i - 1][j - 1] + MOD) % MOD;
                }
                else
                    if(c[i - 1][j] > c[i][j - 1])
                        nr[i][j] = nr[i - 1][j];
                    else
                        nr[i][j] = nr[i][j - 1];
            }
}
int main()
{
    f.getline(s1, NMAX);
    f.getline(s2, NMAX);
    lg1 = strlen(s1);
    lg2 = strlen(s2);
    calcul();
    g << nr[lg1][lg2];
    return 0;
}