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

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

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))   
			{  
				if(a[i][j] == 1)
				{
					nr[i][j] = 1;
				}
				else
				{
					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)  
							{  
								nr[i][j] += nr[ps1[k][i-1]][ps2[k][j-1]]%666013;  
								nr[i][j] %= 666013;  
							}  
						}  
					}  
				}
			}  
		}  
	}  
     
	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(ps1[s1.at(i-1)-'a'][l1] == i && ps2[s2.at(j-1)-'a'][l2] == j)
				{
					n += nr[i][j]%666013;  
					n %= 666013;  
				}
			}
		}
	} 

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