#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()
{
	for(int i = 0;i<=n;++i)
		cnt[i][0] = 1;
	for(int j = 0;j<=m;++j)
		cnt[0][j] = 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;
					if (D[i - 1][j - 1] == D[i - 1][j])
						cnt[i][j] = (cnt[i][j] - cnt[i - 1][j - 1]  + MOD ) % 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;
}