#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[505][505],dp[505][505],bl[505][505];

int main() {
	
	getline(fin, A);
	getline(fin, 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;
				bl[i][j]=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]);
				bl[i][j]=0;
				
				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];
				dp[i][j]%=md;
			}
		}
		
	fout<<dp[a][b]<<"\n";
}