#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=0;j<l1;++j)
		{
			if(s1.at(j) == 'a'+i)
				ps1[i][j] = j;
			else
				ps1[i][j] = (j>0)?ps1[i][j-1]:-1;
		}
		for(int j=0;j<l2;++j)
		{
			if(s2.at(j) == 'a'+i)
				ps2[i][j] = j;
			else
				ps2[i][j] = (j>0)?ps2[i][j-1]:-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(i>1 && ps1[k][i-2] != -1 && j>1 && ps2[k][j-2] != -1)
					{
						if(a[i][j] == a[ps1[k][i-2]][ps2[k][j-2]] + 1)
						{
							proc = true;
							nr[i][j] += nr[ps1[k][i-2]][ps2[k][j-2]];
							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])
			{
				if(!mask[s1.at(i-1)-'a']) 
				{
					mask[s1.at(i-1)-'a'] = true;
					n += nr[i][j];
					n %= 666013;
				}
			}
		}
	}

	cout << n << endl;
	return 0;
}