#include<string.h>
#include<stdio.h>

using namespace std;
 
int i,j;
int v1[505][505], v2[505][505];

char v3[505], v4[505];
 
FILE *f,*s;

int main()
{
    f=fopen("subsir.in","r");
    s=fopen("subsir.out","w");
	
    fscanf(f,"%s\n%s",&v3,&v4);
	
	int A,B;
	
	A=strlen(v3);
	B=strlen(v4);
	
    for(i=1;i<=A;i++)
	{	
        for (j=1;j<=B;j++)
		{	
            if(v3[i-1]==v4[j-1])
            {
                v1[i][j]=v1[i-1][j-1]+1;
                v2[i][j]=v2[i-1][j-1];
				
                if(v2[i][j]==0)
                    v2[i][j]++;
            }
            else if(v1[i-1][j]>v1[i][j-1])
            {
                v1[i][j]=v1[i-1][j];
                v2[i][j]=v2[i-1][j];
            }
            else if(v1[i][j-1]>v1[i-1][j])
            {
                v1[i][j]=v1[i][j-1];
                v2[i][j]=v2[i][j-1];
            }
            else
            {
                v1[i][j]=v1[i-1][j];
                v2[i][j]=v2[i-1][j]+v2[i][j-1];
				
                v2[i][j]%=666013;
				
                if(v1[i-1][j]==v1[i-1][j-1])
                {
                    v2[i][j]-=v2[i-1][j-1];
					
                    v2[i][j]+=666013; 
					v2[i][j]%=666013;
                }
            }
		}	
	}
	
    fprintf(s,"%d",v2[A][B]);
	
	fclose(s);
	
	return 0;
}