#include <iostream>
#include <string>
#include <cstdlib>
#include <fstream>
#define max(a, b) (((a) > (b)) ? (a) : (b))

using namespace std;

int main() {

string s1, s2;

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

in >> s1 >> s2;

int **lcs, i, j;
long long **count;


lcs = (int**)calloc(s1.size() + 1, sizeof(int*));
count = (long long **)calloc(s1.size() + 1, sizeof(long long*));

for (i = 0; i <= s1.size(); i++)
{
	lcs[i] = (int*)calloc(s2.size() + 1, sizeof(int));
	count[i] = (long long *)calloc(s2.size() + 1, sizeof(long long));
}

for (i = 1; i < s1.size() + 1; i++)
	for (j = 1; j < s2.size() + 1; j++)
		if (s1[i-1] == s2[j-1])
		{
			lcs[i][j] = lcs[i - 1][j - 1] + 1;
			count[i][j] = ( count[i-1][j-1] != 0 ? count[i-1][j-1] : 1);
		}
		else
		{
			lcs[i][j] = max (lcs[i][j-1], lcs[i-1][j]);
			if (lcs[i-1][j] == 0 && lcs[i][j-1] == 0) 
				count[i][j] = 0;
			else 
			if(lcs[i-1][j] == lcs[i][j-1])
				count[i][j] =  count[i][j-1] + count[i-1][j] -count[i-1][j-1] * (lcs[i-1][j-1] / lcs[i-1][j]);
			else
				if (lcs[i-1][j] > lcs[i][j-1])
					count[i][j] = count[i-1][j];
				else
					count[i][j] = count[i][j-1];
		}
/*
for (i = 0; i < s1.size() + 1; i++)
{
	cout << endl;
	for (j = 0; j < s2.size() + 1; j++)
		cout << count[i][j] <<" ";
}
*/
out << count[i-1][j-1] % 666013;		
return 0;
}