#include<stdio.h>
#include<string.h>
#define N 666013
char a[505],b[505];
int n,m;
int lsc[505][505],nr[505][505];
////////////////////////////////////////////////////
void rezolvare()
{
	int i,j;
	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];
			}	
			else
			{
				if(lsc[i-1][j]>lsc[i][j-1])
				{
					lsc[i][j]=lsc[i-1][j];
					nr[i][j]=nr[i-1][j];
				}	
				else
				{
					if(lsc[i][j-1]>lsc[i-1][j])
					{
						lsc[i][j]=lsc[i][j-1];
						nr[i][j]=nr[i][j-1];
					}	
					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;
					}	
				}	
			}	
		}	
	}	
}
///////////////////////////////////////////////////
int main()
{
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	scanf("%s",a);//gets(a);
	scanf("%s",b);//gets(b);
	n=strlen(a);
	m=strlen(b);
	rezolvare();
	printf("%d\n",nr[n][m]);
	return 0;
}