#include<cstdio>
#include<cstring>

using namespace std;

const int MAXN = 510;
const int MOD = 666013;

char A[MAXN], B[MAXN];
int d[MAXN][MAXN], sol[MAXN][MAXN], N, M;

inline int maxim(int a, int b)
{
	if(a > b)
		return a;
	return b;
}

int main()
{
	freopen("subsir.in", "r", stdin);
	freopen("subsir.out", "w", stdout);
	
	int i, j;
	
	gets(A + 1);
	gets(B + 1);
	
	N = strlen(A + 1);
	M = strlen(B + 1);
	
	for(i = 0; i <= N; ++i)
		sol[i][0] = 1;
	for(i = 0; i <= M; ++i)
		sol[0][i] = 1;
	
	for(i = 1; i <= N; ++i)
		for(j = 1; j <= M; ++j){
			if(A[i] == B[j]){
				d[i][j] = 1 + d[i - 1][j - 1];
				sol[i][j] = sol[i - 1][j - 1];
			}
			else
				if(d[i - 1][j] == d[i][j - 1]){
					d[i][j] = d[i - 1][j];
					sol[i][j] = (sol[i - 1][j] + sol[i][j - 1]) % MOD;
					
					if(d[i - 1][j] == d[i - 1][j - 1])
						sol[i][j] = (sol[i][j] - sol[i - 1][j - 1] + MOD) % MOD;
				}
				else
					if(d[i - 1][j] > d[i][j - 1]){
						d[i][j] = d[i - 1][j];
						sol[i][j] = sol[i - 1][j];
					}
					else
						if(d[i][j - 1] > d[i - 1][j]){
							d[i][j] = d[i][j - 1];
							sol[i][j] = sol[i][j - 1];
						}
		}
		
		printf("%d", sol[N][M]);
		
		return 0;
}