#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[2][512] , cnt[2][512] , n , m;

void solve()
{
	for(int i = 0;i<2;++i)
		cnt[i][0] = cnt[0][i] = 1;

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

int main()
{
	fin>>s1>>s2;
	n = strlen(s1) , m = strlen(s2);
	solve();
	return 0;
}