#include <fstream>

using namespace std;
string s1,s2;
int md=666013;
int l[515][515],dp[515][515];

int main()
{
    ifstream cin("subsir.in");
    ofstream cout("subsir.out");

    string c1,c2;
    cin>>s1>>s2;
    c1=s1;
    c2=s2;

	for(int i=1;i<=s1.size();i++)
	{
	    for(int j=1;j<=s2.size();j++)
		{
			if(s1[i-1]==s2[j-1])
			{
				l[i][j]=l[i-1][j-1]+1;
				dp[i][j]=dp[i-1][j-1];
				if(l[i][j]==1)	dp[i][j]=1;
			}
			else
			{
				l[i][j]=max(l[i-1][j], l[i][j-1]);

				if(l[i-1][j]==l[i][j])	dp[i][j]+=dp[i-1][j];
				if(l[i][j-1]==l[i][j])	dp[i][j]+=dp[i][j-1];
				if(l[i-1][j-1]==l[i][j] && l[i-1][j]==l[i][j-1])	dp[i][j]-=dp[i-1][j-1]-md;
				dp[i][j]%=md;
			}
		}
	}
	cout<<dp[s1.size()][s2.size()];
    return 0;
}