#include <fstream>
#include <cstring>
#define MOD 666013
using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");
char a[509], b[509];
int n, m, dp[509][509], nr[509][509]; 
int main()
{
	fin >> (a + 1) >> (b + 1);
	n = strlen(a + 1);
	m = strlen(b + 1);
	for(int i=0; i<=n; i++) nr[i][0] = 1;
	for(int i=0; i<=m; i++) nr[0][i] = 1;
	
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			if(a[i] == b[j]) 
			{
				dp[i][j] = dp[i-1][j-1] + 1;
				nr[i][j] = nr[i-1][j-1];
			}
			else if(dp[i][j-1] < dp[i-1][j])
			{
				dp[i][j] = dp[i-1][j];
				nr[i][j] = nr[i-1][j];
			}
			else if(dp[i][j-1] > dp[i-1][j])
			{
				dp[i][j] = dp[i][j-1];
				nr[i][j] = nr[i][j-1];
			}
			else
			{
				dp[i][j] = dp[i-1][j];
				nr[i][j] = (nr[i-1][j] + nr[i][j-1]) % MOD;
				if(dp[i-1][j-1] == dp[i-1][j]) nr[i][j] = (nr[i][j] - nr[i-1][j-1] + MOD) % MOD;
			}
		}
	}
	
	fout << nr[n][m] << '\n';
	fout.close();
	return 0;
}