#include <fstream>
#include <cstring>
#define mod 666013
#define o 530
using namespace std;
char a[o],b[o];
int m,n,c[o][o],mat[o][o];
void rezolva()
{
	//mat[0][0]=mat[1][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(a[i-1]==b[j-1])
			{
			    c[i][j]=c[i-1][j-1]+1;
                mat[i][j]=mat[i-1][j-1];
			 }
			else
				if(c[i-1][j]==c[i][j-1])
				{
				    c[i][j] = c[i-1][j] ;
                    mat[i][j] =(mat[i-1][j]+mat[i][j-1])%mod;
				}
				else
					if(c[i-1][j]>c[i][j-1])
					{
					    c[i][j]=c[i-1][j];
                        mat[i][j]=mat[i-1][j];
					}
					else
					{
						c[i][j]=c[i][j-1];
                        mat[i][j]=mat[i][j-1];
					}
}
int main()
{
    ifstream f("subsir.in");
    ofstream g("subsir.out");

	f.get(a,o);
	f.get();
	f.get(b,o);
	n=strlen(a);
    m=strlen(b);
    rezolva();
	g<<mat[n][m];
}