#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

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

string s1, s2;
//vector<long> a, b;
long lmax, sol;
int a[505][505];

int main()
{
	getline(fin, s1);
	getline(fin, s2);
	fin.close();
	//a.resize(2);
	//a.resize(s2.size());
	//b.resize(s2.size());
	
	int linie = 1;
	/*for (int i = 0; i < s1.size(); i++)
		for ( int j = 0; j < s2.size(); ++j)
		{
			if ( s1[i] == s2[j])
			{
				a[j] = b[j-1] + 1;
				if ( a[j] > lmax)
				{
					lmax = a[j];
					sol = 1;
				}
				if (a[j] == lmax) sol = (sol+1) % 666013;
			}
			else
				a[j] = max(b[j], a[j-1]);
			swap(a, b);
		}*/
	for (int i = 1; i <= s1.size(); i++)
		for ( int j = 1; j <= s2.size(); ++j)
		{
			if ( s1[i-1] == s2[j-1])
			{
				a[i][j] = a[i-1][j-1] + 1;
				if ( a[i][j] == lmax) sol = (sol + 1) % 666013;
				if ( a[i][j] > lmax)
				{
					lmax = a[i][j];
					sol = 1;
				}
			}
			else
				a[i][j] = max(a[i-1][j], a[i][j-1]);
		}
	
		

	fout << sol << '\n';
	fout.close();
	return 0;
}