#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 507;
const int mod = 666013;

string a, b;

int dp[DIM][DIM];
int nr[DIM][DIM];


main()
{
	string a;
	string b;
	
	fin >> a >> b;
	
	int n = a.size();
	int m = b.size();
	
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)
		{
			char x = a[i - 1];
			char y = b[j - 1];
			
			if(x == y)
			{
				dp[i][j] = dp[i - 1][j - 1] + 1;
				nr[i][j] = max(nr[i - 1][j - 1], 1);
			}
			else
			{
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
				
				if(dp[i][j] == dp[i - 1][j])
					nr[i][j] += nr[i - 1][j];
				
				if(dp[i][j] == dp[i][j - 1])
					nr[i][j] += nr[i][j - 1];
				
				if(dp[i - 1][j] == dp[i][j - 1])
					nr[i][j] -= nr[i - 1][j - 1];
				
				nr[i][j] %= mod;
				
				if(nr[i][j] < 0)
					nr[i][j] += mod;
			}
		}
	
	fout << nr[n][m] << '\n';
}