#include <fstream>
#include <cstring>

using namespace std;

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

const int MOD = 666013;
char s1[512] , s2[512];
int D[512][512] , cnt[512][512] , n , m;

void solve()
{
	cnt[0][0] = cnt[1][0] = 1;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(s1[i-1] == s2[j-1]) D[i][j] = D[i-1][j-1] + 1 , cnt[i][j] = cnt[i-1][j-1];
			else
				if(D[i-1][j] == D[i][j-1]) D[i][j] = D[i-1][j] , cnt[i][j] = (cnt[i-1][j] + cnt[i][j-1])%MOD;
				else
					if(D[i-1][j] > D[i][j-1]) D[i][j] = D[i-1][j] , cnt[i][j] = cnt[i-1][j];
					else
						D[i][j] = D[i][j-1] , cnt[i][j] = cnt[i][j-1];
}

int main()
{
	fin>>s1>>s2;
	n = strlen(s1) , m = strlen(s2);
	solve();
	fout<<cnt[n][m];
	return 0;
}