#include<fstream>
#include <cstring>
#define Nmax 502
#define MOD 666013
using namespace std;

char a[Nmax], b[Nmax];
int i, j, cnt[Nmax][Nmax], best[Nmax][Nmax];
int n, m;

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

int main()
{
	fin.getline(a, Nmax);
	fin.getline(b, Nmax);
	n=strlen(a);
	m=strlen(b);
	for(i=0;i<=n;++i)
		cnt[i][0]=1;
	for(i=0;i<=m;++i)
		cnt[0][i]=1;
	
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			if(a[i-1]==b[j-1])
			{	best[i][j]=best[i-1][j-1]+1, cnt[i][j]=cnt[i-1][j-1];}
			else
				if(best[i-1][j]==best[i][j-1])
				{
					best[i][j]=best[i-1][j];
					cnt[i][j]=(cnt[i-1][j]+cnt[i][j-1])%MOD;
					if(best[i-1][j-1]==best[i-1][j])
						cnt[i][j] = (cnt[i][j] - cnt[i - 1][j - 1]  + MOD ) % MOD;
				}
				else
					if(best[i][j-1]>best[i-1][j])
						best[i][j]=best[i][j-1], cnt[i][j]=cnt[i][j-1];
					else
						best[i][j]=best[i-1][j], cnt[i][j]=cnt[i-1][j];
		}
	fout<<cnt[n][m]<<'\n';
	fin.close();
	fout.close();
	return 0;
}