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

using namespace std;

int backtrack(int **lcs, int i, int j, string s1, string s2, int count)
{
	if (i == 0 || j == 0);
		
	else 
		if (s1[i] == s2[j])
			return backtrack(lcs, i - 1, j - 1, s1, s2, count);
		else
		{
			if (lcs[i][j-1] == lcs[i-1][j])
				backtrack (lcs, i, j-1, s1, s2, count ++);
				backtrack (lcs, i-1, j, s1, s2, count ++);	
			if (lcs[i][j-1] > lcs[i-1][j])
				return backtrack(lcs, i, j-1, s1, s2, count);

			if (lcs[i-1][j] >lcs[i][j-1])
				return backtrack(lcs, i-1, j, s1, s2, count);
		}
	return count;
}
			

int main() {

string s1, s2;

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

in >> s1 >> s2;

int **lcs, i, j, count;

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

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

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;
		else
			lcs[i][j] = max (lcs[i][j-1], lcs[i-1][j]);

count = 1;
if (lcs[i-1][j-1] == 0)
	out << 0;
else
	{
		out << backtrack (lcs, i-1, j-1, s1, s2, count) % 666013;
	}

/*
for (i = 0; i <= s1.size(); i++)
	{
	cout <<endl;
	for ( j = 0; j <= s2.size(); j++)
		cout << lcs[i][j] <<" ";
	}
*/

return 0;
}