#include <fstream>
#include <cstring>

using namespace std;

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

#define MOD 666013

char a[505], b[505];
int nrla, nrlb, l[505][505], nr[505][505];

/*Daca a[i]==b[j] lg++ si nr ramane la fel
 *
 * Aftfel l[i][j]=max(l[i-1][j],l[i][j-1])
 * Nr va veni din directia maximului dintre i-1 j, i j-1, i-1 j-1
 * */

int main() {
    f >> (a + 1) >> (b + 1);
    nrla = strlen(a + 1);
    nrlb = strlen(b + 1);
    for (int i = 0; i <= nrla; ++i)
        nr[i][0] = 1;
    for (int j = 0; j <= nrlb; ++j)
        nr[0][j] = 1;
    for (int i = 1; i <= nrla; ++i)
        for (int j = 1; j <= nrlb; ++j) {
            if (a[i] == b[j]) {
                l[i][j] = l[i - 1][j - 1] + 1;
                nr[i][j] = nr[i - 1][j - 1];
            } else {
                l[i][j] = max(l[i - 1][j], l[i][j - 1]);
                if (l[i - 1][j] == l[i - 1][j - 1] && l[i - 1][j] == l[i][j - 1])
                    nr[i][j] = (nr[i - 1][j] + nr[i][j - 1] - nr[i - 1][j - 1] + MOD) % MOD;
                else if (l[i - 1][j] == l[i][j - 1])
                    nr[i][j] = (nr[i - 1][j] + nr[i][j - 1]) % MOD;
                else if (l[i - 1][j] > l[i][j - 1])
                    nr[i][j] = nr[i - 1][j];
                else
                    nr[i][j] = nr[i][j - 1];
            }
        }
    g << nr[nrla][nrlb];
    return 0;
}