#include<stdio.h>
#include<string.h>
#define mod 666013
#define N 507

int m,n,A[N],B[N],v[N][N],nr;
char s1[N],s2[N];

inline int max(int a,int b){
	if(a>b)
		return a;
	return b;
}

void afis(){
	int i,j;
	for(i=0;i<m;++i){
		for(j=0;j<n;++j)
			printf("%d\t",v[i][j]);
		printf("\n");
	}
}

int main(){
	int i,j,p=0,q=0,lmax=0;
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	scanf("%s",s1);
	scanf("%s",s2);
	m=strlen(s1);
	n=strlen(s2);
	for(i=0;i<m;++i)
		for(j=0;j<n;++j){
			if(s1[i]==s2[j]&&i>p&&j>q){
				v[i][j]=(lmax+1)%mod;
				lmax=v[i][j];
				p=i;
				q=j;
			}
			else
				if(s1[i]==s2[j])
					v[i][j]+=(v[i-1][j]+v[i][j-1]+1)%mod;
			else
				v[i][j]=0;
		}
	printf("%d\n",v[m-1][n-1]);
	fclose(stdin);
	fclose(stdout);
	return 0;  
}