#include <cstdio>
#include <cstring>

using namespace std;

int c[501][501],d[501][501];
char a[501],b[501];

int main()
{
    int i,j,n,m;
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","r",stdout);
	fgets(a,sizeof(a),stdin);
	fgets(b,sizeof(b),stdin);
	n=strlen(a);
	m=strlen(b);
	for(i=0;i<=501;i++)
		d[i][0]=d[0][i]=1;
	for(i=0;i<n;++i)
		for(j=0;j<m;++j)
			if(a[i]==b[j])
			{
				c[i+1][j+1]=c[i][j]+1;
				d[i+1][j+1]=d[i][j];
			}
			else if(c[i+1][j]<c[i][j+1])
            {
                c[i+1][j+1]=c[i][j+1];
                d[i+1][j+1]=d[i][j+1];
            }
            else if(c[i+1][j]>c[i][j+1])
            {
                c[i+1][j+1]=c[i+1][j];
                d[i+1][j+1]=d[i+1][j];
            }
            else if(c[i+1][j]==c[i][j+1])
            {
                c[i+1][j+1]=c[i][j+1];
                d[i+1][j+1]=(d[i+1][j]+d[i][j+1])%666013;
                if(c[i][j]==c[i+1][j])
                    d[i+1][j+1]=(d[i+1][j+1]-d[i][j]+666013)%666013;
            }
    printf("%d\n",d[n][m]);
	return 0;
}