// subsir.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
#include <stdlib.h>
#define maxim(a,b) (a>=b?a:b)
char e[503];
char f[503];
int d[501][501];
char c[503][5003];
char sir[501];
int nre()
{
	int i=1;
	while(e[++i]!='\n' && e[i]!=0);
	i--;
	return i;
}
int nrf()
{
	int i=1;
	while(f[++i]!='\n' && f[i]!=0);
	i--;
	return i;
}

void con(int n,int m)
{
	int bst=0,i,j;
	for(i=n,j=m;j;)
		if(e[i]==f[j])
			sir[++bst]=e[i],i--,j--;
		else if(d[i-1][j]<=d[i][j-1])
			j--;
		else
			i--;
}

void scrie(int i,int max)
{

	for(int j=1;j<=max;j++)
		c[i][j]=sir[j];

}

int t(int nr,int max)
{
	int b=1;
	for(int i=1;i<=nr;i++)
	{
		b=1;
		for(int j=1;j<=max;j++)
			if(c[i][j]!=sir[j])
				b=0;
		if(b)
			return 0;
	}

	return 1;
}

int main()
{
	
    int i,j,max=0,nr=0,a,b;
    FILE *f1,*f2;
    f1=fopen("subsir.in","r");
    f2=fopen("subsir.out","w");
    fgets(e+1,503,f1);
    fgets(f+1,503,f1);
	a=nre();
	b=nrf();

	for(i=1;i<=a;i++)
		for(j=1;j<=b;j++)
		{
			if(e[i]==f[j])
			{
				d[i][j]=d[i-1][j-1]+1;
				if(d[i][j]>max)
				{
					con(i,j);
					max=d[i][j];
					nr=1;
					scrie(1,max);
				}
				else if(d[i][j]==max)
				{
					con(i,j);
					if(t(nr,max))
						scrie(++nr,max);
					nr=nr%666013;
				}
			}
			else
				d[i][j]=maxim(d[i-1][j],d[i][j-1]);

		}

    fprintf(f2,"%d",nr%666013);
    fclose(f1);
    fclose(f2);


	return 0;
}