#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>

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

const int MOD = 666013;
std::string str_a, str_b;
int next_a[26][505];
int next_b[26][505];
std::pair<int,int> dp[505][505];

std::pair<int,int> sol(int poz_a, int poz_b) {
	if (dp[poz_a][poz_b].first!=-1) return dp[poz_a][poz_b];
	std::cout << poz_a << " " << poz_b << "\n";

	dp[poz_a][poz_b].first = 1;
	dp[poz_a][poz_b].second = 1;
	for (int i = 0; i < 26; i++) {
		if (next_a[i][poz_a+1]!=-1&&next_b[i][poz_b+1]!=-1) {
			std::pair<int,int> cand = sol(next_a[i][poz_a+1],next_b[i][poz_b+1]);
			if (dp[poz_a][poz_b].first<cand.first+1) {
				dp[poz_a][poz_b].first = cand.first+1;
				dp[poz_a][poz_b].second = cand.second;
			}
			else if (dp[poz_a][poz_b].first==cand.first+1) {
				dp[poz_a][poz_b].second += cand.second;
				if (dp[poz_a][poz_b].second>=MOD) {
					dp[poz_a][poz_b].second -= MOD;
				}
			}
		}
	}

	return dp[poz_a][poz_b];
}

int main() {
	memset(dp,-1,sizeof(dp));
	fin >> str_a >> str_b;

	for (int c = 0; c < 26; c++) {
		next_a[c][str_a.size()] = next_b[c][str_b.size()] = -1;
		for (int i = str_a.size()-1; i >= 0; i--) {
			if (str_a[i]==c+'a') next_a[c][i] = i;
			else next_a[c][i] = next_a[c][i+1];
		}
		for (int i = str_b.size()-1; i >= 0; i--) {
			if (str_b[i]==c+'a') next_b[c][i] = i;
			else next_b[c][i] = next_b[c][i+1];
		}
	}

	std::pair<int,int> ret(0,0);
	for (int i = 0; i < 26; i++) {
		if (next_a[i][0]!=-1&&next_b[i][0]!=-1) {
			std::pair<int,int> cand = sol(next_a[i][0],next_b[i][0]);
			if (ret.first<cand.first) {
				ret = cand;
			}
			else if (ret.first==cand.first) {
				ret.second += cand.second;
				if (ret.second>=MOD) {
					ret.second -= MOD;
				}
			}
		}
	}

	fout << ret.second << "\n";
	//fout << ret.first << " " << ret.second << "\n";
}