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

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

const int r = 666013;

string a, b;
int dp[501][501], nr[501][501];
int ca[501], cb[501];

//ca[j] = ultimul caracter din a cu care s-a combinat b[j]
//cb[i] = ultimul caracter din b cu care s-a combinat a[i]

int main()
{
    int i, j, n, m;
    bool oki, okj;
    fin >> a >> b;

    n = a.size();
    m = b.size();

    a = '#' + a;
    b = '#' + b;

    for (i = 0; i<=n; i++)
        nr[i][0] = 1;
    for (i = 0; i<=m; i++)
        nr[0][i] = 1;

    for (i = 1; i<=n; i++)
    {
        for (j = 1; j<=m; j++)
        {
            if (a[i] == b[j])
            {
                dp[i][j] = 1 + dp[i-1][j-1];
                nr[i][j] = nr[i-1][j-1]; //bijectie

                ca[j] = i;
                cb[i] = j;
            }
            else
            {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

                oki = okj = 0;
                //oki, okj imi arata daca a[i] (rasp. b[i]) CHIAR au contribuit la dp[i][j] sau
                //sunt doar balast ce poate fi ignorat

                if (cb[i] > 0 && dp[i][cb[i]] == dp[i][j]) //deci a[i] chiar a contribuit la dp[i][j]
                    oki = 1;
                if (ca[j] > 0 && dp[ca[j]][j] == dp[i][j]) //deci b[j] chiar a contribuit la dp[i][j]
                    okj = 1;

                if (oki == 1)
                {
                    if (okj == 1)
                    {
                        if (dp[i-1][j-1] == dp[i][j]) //deci exista "caractere intermediare"
                        {
                            //nr[i][j] = (nr[i-1][j-1] + nr[i][cb[i]] + nr[ca[j]][j]) % r;
                            //linia de mai sus esueaza pe cazul: ba abb
                            nr[i][j] = (nr[i][j-1] + nr[i-1][j] - nr[i-1][j-1] + r)%r;
                        }
                        else //nu avem "caractere intermediare"
                            nr[i][j] = (nr[i][cb[i]] + nr[ca[j]][j]) % r;
                    }
                    else
                        nr[i][j] = nr[i][j-1]; //b[j] e balast, poate fi eliminat/ignorat fara nicio treaba
                }
                else if (okj == 1)
                    nr[i][j] = nr[i-1][j]; //a[i] e balast
                else
                    nr[i][j] = nr[i-1][j]; //ambele sunt balast, puteam pune si nr[i][j] = nr[i][j-1]
            }
        }
    }

    fout << nr[n][m];
    return 0;
}