#include <fstream>
#include <cstring>
using namespace std;
#define MAX_N 501
#define MOD 666013

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

char a[MAX_N];
char b[MAX_N];

int nr[MAX_N][MAX_N]; // nr[i][j] - nr de subs comune de lung max intre a[1..i] si b[1..j]
int d[2][MAX_N];
int n;
int m;
void Read();

int Lmax2();
void Debug();

int main()
{
	Read();
	int lmax = Lmax2();
    fout << nr[n][m]<< '\n';
	fin.close();
	fout.close();
	return 0;
}


int Lmax2()
{
	int c = 1, p = 0;
	for ( int i = 0; i <= n; ++i )
		nr[i][0]  = 1;
	for ( int i = 0; i <= m; ++i )
		nr[0][i]  = 1;		
	for ( int i = 1; i <= n; ++i, c = !c, p = !p )
		for  (int j = 1; j <= m; ++j )
			if ( a[i-1] == b[j-1] )
			{
				d[c][j] = d[p][j-1] + 1;
				nr[i][j] = nr[i-1][j-1];
			}
			else
			{
				if ( d[p][j] > d[c][j-1] )
				{
					d[c][j] = d[p][j];
					nr[i][j] = nr[i-1][j];
				}
				else
				if ( d[p][j] < d[c][j-1] )
				{
					d[c][j] = d[c][j-1];
					nr[i][j] = nr[i][j-1];
				}
				else
				if ( d[p][j] == d[c][j-1] )
				{
					d[c][j] = d[c][j-1];
					nr[i][j] = (nr[i-1][j] + nr[i][j-1]) % MOD;
					if ( d[p][j] == d[p][j-1] )
						nr[i][j] = (nr[i][j] - nr[i-1][j-1] + MOD) % MOD;
				}		
			}
				
	return d[p][n];
}

void Read()
{
	fin.getline(a, 501);
	n = strlen(a);
	fin.getline(b, 501);
	m = strlen(b);
}