#include <fstream>
#include <algorithm>
#include<cstring>

#define MOD 666013

using namespace std;

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

char a[510], b[510];

int dp[505][505], sol[505][505];

int main() {

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

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

	for (int i = 0; i <= n || i <= m; i++) 
		sol[i][0] = sol[0][i] = 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;
				sol[i][j] = sol[i - 1][j - 1];
			
			}
			else{
				if (dp[i - 1][j] > dp[i][j - 1]) {

					dp[i][j] = dp[i - 1][j];
					sol[i][j] = sol[i - 1][j];

				}
				else
					if (dp[i][j - 1] > dp[i - 1][j]) {

						dp[i][j] = dp[i][j - 1];
						sol[i][j] = sol[i][j - 1];

					}
					else {

						dp[i][j] = dp[i - 1][j];
						sol[i][j] = sol[i - 1][j] + sol[i][j - 1];

						if (sol[i][j] >= MOD)
							sol[i][j] -= MOD;

						if (dp[i][j] == dp[i - 1][j - 1]){
							sol[i][j] -= sol[i - 1][j - 1];
							if (sol[i][j] < 0)
								sol[i][j] += MOD;
						}
					}
			}

		}

	fout << sol[n][m] << "\n";

	return 0;
}

//Miriam e tare!