#include<iostream>
#include<string>
using namespace std;

int a[501][501];
int ps1[27][501];
int ps2[27][501];
int nr[501][501];
bool mask[27];

int main(void)
{
	freopen("subsir.in", "r", stdin);
	freopen("subsir.out", "w", stdout);
	string s1;
	string s2;
	cin >> s1 >> s2;
	int l1 = s1.length();
	int l2 = s2.length();
	for(int i=0;i<=l1;++i)
		a[i][0] = 0;
	for(int i=0;i<=l2;++i)
		a[0][i] = 0;
	for(int i=1;i<=l1;++i)
	{
		for(int j=1;j<=l2;++j)
		{
			if(s1.at(i-1) == s2.at(j-1))
				a[i][j] = a[i-1][j-1] + 1;
			else
				a[i][j] = max(a[i-1][j], a[i][j-1]);
		}
	}

	memset(ps1, 0, sizeof(ps1));
	memset(ps2, 0, sizeof(ps2));
	for(int i=0;i<=26;++i)
	{
		for(int j=1;j<=l1;++j)
		{
			if(s1.at(j-1) == 'a'+i)
				ps1[i][j] = j;
			else
				ps1[i][j] = ps1[i][j-1];
		}
		for(int j=1;j<=l2;++j)
		{
			if(s2.at(j-1) == 'a'+i)
				ps2[i][j] = j;
			else
				ps2[i][j] = ps2[i][j-1];
		}
	}

	memset(nr, 0, sizeof(nr));
	for(int i=1;i<=l1;++i)
	{
		for(int j=1;j<=l2;++j)
		{
			if(s1.at(i-1) == s2.at(j-1)) 
			{
				bool proc = false;
				for(int k=0;k<=26;++k)
				{
					if(ps1[k][i-1] != 0 && ps2[k][j-1] != 0)
					{
						if(a[i][j] == a[ps1[k][i-1]][ps2[k][j-1]] + 1)
						{
							proc = true;
							nr[i][j] += nr[ps1[k][i-1]][ps2[k][j-1]]%666013;
							nr[i][j] %= 666013;
						}
					}
				}
				if(!proc)
					nr[i][j] = 1;
			}
		}
	}
	
	memset(mask, false, sizeof(mask));
	int n = 0;
	for(int i=1;i<=l1;++i)
	{
		for(int j=1;j<=l2;++j)
		{
			if(a[i][j] == a[l1][l2] && s1.at(i-1) == s2.at(j-1))
			{
				if(!mask[s1.at(i-1)-'a']) 
				{
				/*	bool proc = true;
					for(int k=i+1;k<=l1;++k)
						if(s1.at(i-1) == s1.at(k-1))
							proc = false;
					for(int k=i+1;k<=l2;++k)
						if(s2.at(i-1) == s2.at(k-1))
							proc = false;

					if(proc)
					{
				*/		n += nr[i][j]%666013;
						n %= 666013;
				//	}
						mask[s1.at(i-1)-'a'] = true;
				}
			}
		}
	}
	cout << n << endl;
	return 0;
}