#include <fstream>
#include <string.h>
#define MOD 666013
#define NMax 512
using namespace std;
ifstream f("subsir.in");
ofstream g("subsir.out");
int n, m, i, j, d[NMax][NMax], numcl[NMax][NMax], lena, lenb;
char a[NMax], b[NMax];
int getmax(int a, int b)
{
	if (a > b) return a;
	else return b;
}
int main()
{
	f.get(a + 1, 512);
	f.get();
	f.get(b + 1, 512);
	lena = strlen(a + 1);
	lenb = strlen(b + 1);
	for (i = 0; i <= lena; i++)
		numcl[i][0] = 1;
	for (j = 0; j <= lenb; j++)
		numcl[0][j] = 1;
	for (i = 1; i <= lena; i++) {
		for (j = 1; j <= lenb; j++) {
			if (a[i] == b[j]) {
				d[i][j] = d[i - 1][j - 1] + 1;
				numcl[i][j] = numcl[i - 1][j - 1];
			}
			else {
				d[i][j] = getmax(d[i - 1][j], d[i][j - 1]);
				if (d[i - 1][j] == d[i][j - 1]) {
					numcl[i][j] = numcl[i - 1][j] + numcl[i][j - 1];
					if (d[i - 1][j - 1] == d[i - 1][j])
						numcl[i][j] = (numcl[i][j] + 5 * MOD - numcl[i - 1][j - 1]) % MOD;
				}
				else if (d[i - 1][j] > d[i][j - 1])
					numcl[i][j] = numcl[i - 1][j];
				else
					numcl[i][j] = numcl[i][j - 1];
			}
		}
	}
	g << numcl[lena][lenb];
	return 0;
}