#include <bits/stdc++.h>

using namespace std;

char a[502], b[502];
int n, m, dp[502][502], cnt[502][502];

const int mod = 666013;

void reduce(int &x) {
	while(x < 0) x += mod;
	while(x >= mod) x -= mod;
}

int main() {
	ifstream cin("subsir.in");
	ofstream cout("subsir.out");

	cin >> (a + 1) >> (b + 1);

	n = strlen(a + 1);
	m = strlen(b + 1);

	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j)  {
		  if(a[i] == b[j]) {
			dp[i][j] = dp[i - 1][j - 1] + 1;
		  }
		  else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}

	for(int i = 0; i <= m; ++i) cnt[0][i] = 1;
	for(int i = 0; i <= n; ++i) cnt[i][0] = 1;

	for(int i = 1; i <= n; ++i)
	{
		for(int j = 1; j <= m; ++j) {
			if(a[i] == b[j]) {
				cnt[i][j] = cnt[i - 1][j - 1]; // contine pe i si j
			}
			else {
				int mx = max(dp[i - 1][j], dp[i][j - 1]);
				if(dp[i - 1][j] == mx) cnt[i][j] += cnt[i - 1][j];
				if(dp[i][j - 1] == mx) cnt[i][j] += cnt[i][j - 1];
				if(dp[i - 1][j - 1] == mx) {
					cnt[i][j] -= cnt[i - 1][j - 1]; // pe astea le numar de 2 ori
				}

				reduce(cnt[i][j]);
			}
		}
	}


	cout << cnt[n][m];
}