#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
const int Nmax = 505, mod = 666013;
string y, x, a = "1", b = "2";
int d[Nmax][Nmax], nr[Nmax][Nmax], n, m;
int main()
{
    freopen("subsir.in", "r", stdin);
    freopen("subsir.out", "w", stdout);
	getline(cin, x);
	getline(cin, y);
	a += x;
	b += y;
	m = x.size() + 1, n = y.size() + 1;
	for (int i = 0; i <= max(m, n); ++i)
		nr[0][i] = nr[i][0] = 1;
	for (int i = 1; i <= m; ++i)
		for (int j = 1; j <= n; ++j)
			if (a[i] == b[j])
            {
				d[i][j] = d[i-1][j-1] + 1;
				nr[i][j] = nr[i-1][j-1];
			}
			else
				if (d[i][j-1] == d[i-1][j])
				{
					d[i][j] = d[i][j-1];
					nr[i][j] = (nr[i][j-1] + nr[i-1][j]) % mod;
					if (d[i][j] == d[i-1][j-1])
						nr[i][j] = (nr[i][j] - nr[i-1][j-1] + mod) % mod;
				}
			else
				if (d[i][j-1] > d[i-1][j])
				{
					d[i][j] = d[i][j-1];
					nr[i][j] = nr[i][j-1];
				}
			else
				if (d[i-1][j] > d[i][j-1])
				{
					d[i][j] = d[i-1][j];
					nr[i][j] = nr[i-1][j];
				}
	cout<<nr[m][n];
	return 0;
}