// 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];
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;
}

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)
				{
					max=d[i][j];
					nr=1;
				}
				else if(d[i][j]==max)
				{
					nr++;
					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;
}