#include<stdio.h>
#include<string.h>
#define N 666013
char a[505],b[505];
int n,m;
long lsc[505][505],nr[505][505];

int main()
{
	int i,j;
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	gets(a);
	n=strlen(a);
	gets(b);
	m=strlen(b);
	for(i=0;i<=n;i++)
		nr[i][0]=1;
	for(j=0;j<=m;j++)
		nr[0][j]=1;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(a[i]==b[j])
			{	
				lsc[i][j]=1+lsc[i-1][j-1];
				nr[i][j]=nr[i-1][j-1]%N;
			}
			else
			{
				if(lsc[i-1][j]>lsc[i][j-1])
				{
					lsc[i][j]=lsc[i-1][j];
					nr[i][j]=nr[i-1][j]%N;
				}	
				else
				{
					if(lsc[i][j-1]>lsc[i-1][j])
					{
						lsc[i][j]=lsc[i][j-1];
						nr[i][j]=nr[i][j-1]%N;
					}
					else
					{
						lsc[i][j]=lsc[i-1][j];
						nr[i][j]=(nr[i][j-1]+nr[i-1][j])%N;
						if(lsc[i-1][j-1]==lsc[i-1][j])
							nr[i][j]=(nr[i][j]-nr[i-1][j-1]+N)%N;
					}
				}
			}
		}	
	}
	printf("%ld\n",nr[n][m]);
	return 0;
}