//https://infoarena.ro/problema/subsir
#include<fstream>
#include<cstring>
#define Dmax 501
std::ifstream f ("subsir.in");
std::ofstream g ("subsir.out");
int i,j,l1,l2;
char s1[Dmax],s2[Dmax];
int sub[Dmax][Dmax],l[Dmax][Dmax];
int main()
{
    f.getline(s1,Dmax);
    f.getline(s2,Dmax);
    l1=strlen(s1);
    l2=strlen(s2);
    for(i=1;i<=l1;i++)
    for(j=1;j<=l2;j++)
	if(s1[i - 1] == s2[j - 1])
		sub[i][j] = 1 + sub[i - 1][j - 1];
	else
		sub[i][j] = std::max(sub[i][j - 1], sub[i - 1][j]);

    int pre1[l1 + 1][26], pre2[l2 + 1][26];
	
	memset(pre1, -1, sizeof(pre1));
	memset(pre2, -1, sizeof(pre2));

    for(int i = 1;i <= l1;++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 <= l2;++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 <= l1;++i)
		for(int j = 1;j <= l2;++j)
		{
			for(int k = 0;k < 26;++k)
			{
				int i1 = pre1[i][k];
				int i2 = pre2[j][k];
				
				if(i1 != -1 && i2 != -1)
				{
					if(sub[i][j] == 1)
						++l[i][j];
					else if(sub[i1 - 1][i2 - 1] + 1 == sub[i][j])
					{
						l[i][j] += l[i1 - 1][i2 - 1];
						l[i][j] %= 666013;
					}
				}
			}
		}
    g<<l[l1][l2];
    f.close();
    g.close();
    return 0;
        
}