#include <fstream>
#include <cstring>
#define DIM 505
#define MOD 666013
#define infile "subsir.in"
#define outfile "subsir.out"

using namespace std;

ifstream f(infile);
ofstream g(outfile);

char a[DIM], b[DIM];

int D[DIM][DIM], Ans[DIM][DIM];

int main() {
	f >> a + 1 >> b + 1;
	int n = strlen(a + 1);
	int m = strlen(b + 1);
	for (int i = 0; i <= n; ++i)
		Ans[i][0] = 1;
	for (int j = 0; j <= m; ++j)
		Ans[0][j] = 1;
	for (int i = 1; i <= n; ++i)
	for (int j = 1; j <= m; ++j)
	if (a[i] == b[j]) {
		D[i][j] = D[i - 1][j - 1] + 1;
		Ans[i][j] = Ans[i - 1][j - 1];
	}
	else
	if (D[i][j - 1] < D[i - 1][j]) {
		D[i][j] = D[i - 1][j];
		Ans[i][j] = Ans[i - 1][j];
	}
	else
	if (D[i][j - 1] > D[i - 1][j]) {
		D[i][j] = D[i][j - 1];
		Ans[i][j] = Ans[i][j - 1];
	}
	else {
		D[i][j] = D[i - 1][j];
		Ans[i][j] = (Ans[i - 1][j] + Ans[i][j - 1]) % MOD;
		if (D[i - 1][j - 1] == D[i - 1][j])
			Ans[i][j] = (Ans[i][j] - Ans[i - 1][j - 1] + MOD) % MOD;
	}
	/*for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j)
			g << Ans[i][j] << " ";
		g << "\n";
	}*/
	g << Ans[n][m];
	return 0;
}

//This room. This bullet. There's a bullet for everyone. And a time. And a place. Yes... maybe this is how it has to be. - 47