#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
const int NMAX = 501;
const int MMAX = 501;
const int MOD = 666013;
const int INF = 1000000000;
using namespace std;

char A[NMAX], B[NMAX];
int N, M;
int ua[NMAX]['z' - 'a' + 1];
int ub[NMAX]['z' - 'a' + 1];
int C[NMAX][MMAX];
int NR[NMAX][MMAX];
int REZ = 0;
int maxim = 0;
int ulta['z' - 'a' + 1], ultb['z' - 'a' + 1];
pair<int, int> sol[NMAX * MMAX];

void citeste()
{
	gets(A+1);
	N = strlen(A + 1);
	while(!('a' <= A[N] && A[N] <= 'z'))
		N--;
	gets(B+1);
	M = strlen(B + 1);
	while(!('a' <= B[M] && B[M] <= 'z'))
		M--;
}

void write()
{
	//printf("%d %d\n", N, M);
	/*for(int i = 1 ; i <= N ; i++)
		printf("%d ", A[i]);
	printf("\n");
	for(int i = 1 ; i <= M ; i++)
		printf("%d ", B[i]);
	printf("\n");*/
	/*for(int i = 1 ; i <= N ; i++)
	{
		for(int j = 1 ; j <= M ; j++)
			printf("%d ", C[i][j]);
		printf("\n");
	}*/
	//printf("\n");
	/*for(int i = 1 ; i <= N ; i++)
	{
		for(int j = 0; j < 'z' - 'a' ; j++)
			printf("%d ", ua[i][j]);
		printf("\n");
	}*/
	//printf("\n\n\n");
	/*for(int i = 1 ; i <= M ; i++)
	{
		for(int j = 0; j < 'z' - 'a' ; j++)
			printf("%d ", ub[i][j]);
		printf("\n");
	}
	printf("\n\n\n");*/
	/*for(int i = 1 ; i <= N ; i++)
	{
		for(int j = 1 ; j <= M ; j++)
			printf("%d ", NR[i][j]);
		printf("\n");
	}
	printf("\n\n\n");*/
}

void proc()
{
	string :: iterator it;
	for(int i = 1 ; i <= N ; ++i)
		for(int c = 'a' ; c <= 'z' ; ++c)
		{
			ua[i][c -'a'] = ulta[c - 'a'];			
			if(A[i] == c)
				ulta[c - 'a'] = i;
		}
		
	for(int i = 1 ; i <= M ; ++i)
		for(int c = 'a' ; c <= 'z' ; ++c)
		{
			ub[i][c - 'a'] = ultb[c - 'a'];
			if(B[i] == c)
				ultb[c - 'a'] = i;
		}
}

void form()
{
	for(int i = 1 ; i <= N ; ++i)
		for(int j = 1 ; j <= M ; ++j)
			if(A[i] == B[j])
				C[i][j] = C[i-1][j-1] + 1;
			else
				C[i][j] = max(C[i-1][j], C[i][j-1]);
}

void dinamic()
{
	for(int i = 1 ; i <= N ; i++)
		for(int j = 1 ; j <= M ; j++)
			if(C[i][j] == 1 && A[i] == B[j])
				NR[i][j]++;
			
	for(int i = 1 ; i <= N ; i++)
		for(int j = 1 ; j <= M ; j++)
			if(A[i] == B[j])
				for(int c = 'a' ; c <= 'z' ; ++c)
				{
					int ii = ua[i][c - 'a'], jj = ub[j][c - 'a'];
					if(ii && jj)
 						if(C[i][j] == C[ii][jj] + 1)
							NR[i][j] = (NR[i][j] + NR[ii][jj]) % MOD;
				}					
}

void det_max()
{
	for(int i = 1 ; i <= N ; i++)
		for(int j = 1 ; j <= M ; j++)
			if(NR[i][j])
				maxim = max(maxim, C[i][j]);
}

bool incad(int x, int y)
{
	int minim = INF, poz;
	for(int i = 1 ; i <= sol[0].first ; i++)
		if(A[sol[i].first] == A[x] && B[sol[i].second] == B[y])
		{
			if(x < sol[i].first && y < sol[i].second)
				continue;
			if(x > sol[i].first && y > sol[i].second)
				continue;
			if(NR[sol[i].first][sol[i].second] < minim)
			{
				minim = NR[sol[i].first][sol[i].second];
				poz = i;
			}
		}
	
	if(minim != INF)
	{
		if(minim < NR[x][y])
		{
			REZ = MOD + REZ - NR[sol[poz].first][sol[poz].second];
			sol[poz].first = x;
			sol[poz].second = y;
			return 1;
		}
		return 0;
	}
	sol[++sol[0].first] = make_pair(x, y);
	return 1;
}

void scrie()
{
	for(int i = 1 ; i <= N ; i++)
		for(int j = 1 ; j <= M ; j++)
			if(C[i][j] == maxim && incad(i, j))
				REZ = (REZ + NR[i][j]) % MOD;
	cout << REZ << '\n';
}

int main()
{
	freopen("subsir.in", "r", stdin);
	freopen("subsir.out", "w", stdout);
	citeste();
	proc();
	form();
	dinamic();
	det_max();
	write();
	scrie();
	
	return 0;
}