#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

#define MOD 666013

struct Result {
	int len;
	vector<int> subsequence;
};

class Task {
 public:
	void solve() {
		read_input();
		print_output(get_result());
	}

 private:
	string s1;
	string s2;

	void read_input() {
		ifstream fin("subsir.in");
		fin >> s1 >> s2;
		fin.close();
		
		s1 = " " + s1;
		s2 = " " + s2;
	}

	int get_result() {
		Result result;
		result.len = 0;

		vector<char> v;
		vector<char> w;

		v.push_back(' ');
		w.push_back(' ');

		int n = s1.length() - 1;
		int m = s2.length() - 1;

		for (int i = 1; i <= n; ++i) {
			v.push_back(s1[i]);
		}
		for (int i = 1; i <= m; ++i) {
			w.push_back(s2[i]);
		}

		vector < vector<int> > dp(n + 1);
		for (int i = 0; i <= n; ++i) {
			dp[i].resize(m + 1);
		}

		vector < vector<int> > colour(n + 1);
		for (int i = 0; i <= n; ++i) {
			colour[i].resize(m + 1);
		}

		for (int i = 0; i <= n; ++i) {
			for (int j = 0; j <= m; ++j) {
				colour[i][j] = 0;
			}
		}

		//caz de baza
		for (int i = 1; i <= n; ++i) {
			dp[i][0] = 0;
		}
		for (int j = 0; j <= m; ++j) {
			dp[0][j] = 0;
		}

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

		int nr = 0;

		result.len = dp[n][m];
		if (dp[n][m] > 0) {
			++nr;
		}

		int i = n, j = m;
		while (i > 0 && j > 0) {
			colour[i][j] = 1;
			if (v[i] == w[j]) {
				//result.subsequence.push_back(v[i]);
				i--;
				j--;
			}
			else {
				if (dp[i - 1][j] > dp[i][j - 1]) {
					i--;
				}
				else {
					if (dp[i - 1][j] < dp[i][j - 1]) {
						j--;
					}
					else {
						i--;
						nr = (nr * 2) % MOD;///
					}
				}
			}
		}

		//reverse(result.subsequence.begin(), result.subsequence.end());

		return nr;
	}

	void print_output(int number) {
		ofstream fout("subsir.out");
		fout << number << '\n';
		fout.close();
	}
};

int main() {
	Task task;
	task.solve();
	return 0;
}