#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");

string A,B;
int a,b,i,j,md=666013;
int l[515][515],dp[515][515];

int main() {
	
	fin>>A>>B;
	a=(int)A.size();
	b=(int)B.size();
		
	for(i=1;i<=a;i++)
		for(j=1;j<=b;j++)
		{
			if(A[i-1]==B[j-1])
			{
				l[i][j]=l[i-1][j-1]+1;
				dp[i][j]=dp[i-1][j-1];
				if(l[i][j]==1)	dp[i][j]=1;
			}
			else
			{
				l[i][j]=max(l[i-1][j], l[i][j-1]);
				
				if(l[i-1][j]==l[i][j])	dp[i][j]+=dp[i-1][j];
				if(l[i][j-1]==l[i][j])	dp[i][j]+=dp[i][j-1];
				if(l[i-1][j-1]==l[i][j] && l[i-1][j]==l[i][j-1])	dp[i][j]-=dp[i-1][j-1]-md;
				dp[i][j]%=md;
			}
		}
	
	fout<<dp[a][b]<<"\n";
	
	/*- Ce te legeni, codrule,
	 Fără ploaie, fără vânt,
	 Cu crengile la pământ?
	 - De ce nu m-aş legăna,
	 Dacă trece vremea mea!
	 Ziua scade, noaptea creşte
	 Şi frunzişul mi-l răreşte.
	 Bate vântul frunza-n dungă -
	 Cântăreţii mi-i alungă;
	 Bate vântul dintr-o parte -
	 Iarna-i ici, vara-i departe.*/
}