#include <bits/stdc++.h>
using namespace std;

int solve(const string& s1, const string& s2)
{
	int n1 = s1.size(), n2 = s2.size();
	int c[n1 + 1][n2 + 1], l[n1 + 1][n2 + 1];
	memset(c, 0, sizeof(c));
	memset(l, 0, sizeof(l));
	
	const int mod = 666013;
	for(int i = 1;i <= n1;++i)
		for(int j = 1;j <= n2;++j)
		{
			if(s1[i - 1] == s2[j - 1])
				c[i][j] = 1 + c[i - 1][j - 1];
			else
				c[i][j] = max(c[i][j - 1], c[i - 1][j]);
		}
	
	int pre1[n1 + 1][26], pre2[n2 + 1][26];
	
	memset(pre1, -1, sizeof(pre1));
	memset(pre2, -1, sizeof(pre2));
	for(int i = 1;i <= n1;++i)
	{
		for(int j = 0;j < 26;++j)
			pre1[i][j] = pre1[i - 1][j];
		pre1[i][s1[i - 1] - 'a'] = i;
	}
	for(int i = 1;i <= n2;++i)
	{
		for(int j = 0;j < 26;++j)
			pre2[i][j] = pre2[i - 1][j];
		pre2[i][s2[i - 1] - 'a'] = i;
	}
	
	for(int i = 1;i <= n1;++i)
		for(int j = 1;j <= n2;++j)
		{
			for(int k = 0;k < 26;++k)
			{
				int i1 = pre1[i][k];
				int i2 = pre2[j][k];
				
				if(i1 != -1 && i2 != -1)
				{
					if(c[i][j] == 1)
						++l[i][j];
					else if(c[i1 - 1][i2 - 1] + 1 == c[i][j])
					{
						l[i][j] += l[i1 - 1][i2 - 1];
						l[i][j] %= mod;
					}
				}
			}
		}
	return l[n1][n2];
}

int main() {
	freopen("subsir.in", "r", stdin);
	freopen("subsir.out", "w", stdout);
	string s1, s2;
	cin >> s1 >> s2;
	cout << solve(s1, s2);
}