#include<cstdio>
#include<cstring>

using namespace std;

const int MaxN = 1 << 9,Mod = 666013;
char a[MaxN],b[MaxN];
int N,M,DP[MaxN][MaxN],S[MaxN][MaxN];

int main ()
{
	freopen("subsir.in" , "r" , stdin);
	scanf("%s" , a+1);scanf("%s" , b+1);
	N = strlen(a+1);
	M = strlen(b+1);
	int i,j;
	for(i = 0 ; i <= N ; i++)
		S[i][0] = 1;
	for(j = 0 ; j <= M ; j++)
		S[0][j] = 1;
	for( i = 1 ; i <= N ; i++)
		for( j = 1 ; j <= M ; j++)
			{
				if( a[i] == b[j] )
					{
						DP[i][j] = DP[i-1][j-1] + 1;
						S[i][j] = S[i-1][j-1];
					}
					else
					if( DP[i-1][j] == DP[i][j-1])
						{
							DP[i][j] = DP[i-1][j];
							S[i][j] = (S[i-1][j] + S[i][j-1]) % Mod;
							if(DP[i-1][j-1] == DP[i-1][j])
								S[i][j] = (S[i][j] - S[i-1][j-1] + Mod) % Mod;
						}
						else
						if( DP[i-1][j] > DP[i][j-1])
							{
								DP[i][j] = DP[i-1][j];
								S[i][j] = S[i-1][j];
							}
							else
							if( DP[i-1][j] < DP[i][j-1])
								{
									DP[i][j] = DP[i][j-1];
									S[i][j] = S[i][j-1];
								}
			}
	freopen("subsir.out" , "w" , stdout);
	printf("%d\n" , S[N][M]);
	return 0;
}