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

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

const int N = 505, mod = 666013;

string y, x, a = "1", b = "2";
int d[N][N], nr[N][N], n, m;

int main() {
	fin >> x >> 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];
				}
	fout << nr[m][n];
}