#include<fstream>
#define mod 666013
using namespace std;

int i,j,n,m,l[501][501],a[501][501];
char s1[501],s2[501];
void det()
{
	int i,j;
	for(i=0;i<=501;i++)
		a[i][0]=a[i][1]=1;
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
			if(s1[i]==s2[j])
			{
				l[i+1][j+1]=l[i][j]+1;
				a[i+1][j+1]=a[i][j];
			}
			else
				if(l[i+1][j]<l[i][j+1])
				{
					l[i+1][j+1]=l[i][j+1];
					a[i+1][j+1]=a[i][j+1];
				}
				else
					if(l[i+1][j]>l[i][j+1])
				{
					l[i+1][j+1]=l[i+1][j];
					a[i+1][j+1]=a[i+1][j];
				}
					else
						if(l[i+1][j]==l[i][j+1])
						{
							l[i+1][j+1]=l[i][j+1];
							a[i+1][j+1]=(a[i+1][j]+a[i][j+1])%mod;
							if(l[i][j]==l[i+1][j])
								a[i+1][j+1]=(a[i+1][j+1]-a[i][j]+mod)%mod;
						}
}
int main()
{
	ifstream f("subsir.in");
	ofstream g("subsir.out");
	f.getline(s1,501);
	f.getline(s2,501);
	n=strlen(s1);
	m=strlen(s2);
	det();
	g<<a[n][m]<<"\n";
	return 0;
}