#include <fstream>
#include <string.h>
using namespace std;

ifstream r("subsir.in");
ofstream w("subsir.out");
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MOD 666013
char s1[501],s2[501]; int c[501][501],nr[501][501];
int i,j;

int LCSLength()
{
	int n=MAX(strlen(s1),strlen(s2));
	for(i=0;i<=n;i++) { nr[i][0]=1; nr[0][i]=1; }
	
	for(i=1;i<=strlen(s1);i++)
		for(j=1;j<=strlen(s2);j++)
			if(s1[i]==s2[j]) 
			{ c[i][j]=c[i-1][j-1]+1; nr[i][j]=nr[i-1][j-1];  }
			else
			{ 
				if(c[i][j-1]!=c[i-1][j])
				{
					c[i][j] = MAX(c[i-1][j],c[i][j-1]);
					nr[i][j] = MAX(nr[i][j-1],nr[i-1][j]);
				}
				else
				{
					c[i][j] = c[i][j-1];
					nr[i][j] = (nr[i-1][j] + nr[i][j-1] ) % MOD;
                    if(c[i-1][j-1] == c[i][j] ) nr[i][j]=(nr[i][j] - nr[i-1][j-1] + MOD )%MOD;
				}

			}
	
	return nr[strlen(s1)][strlen(s2)];
}				


int main()
{
	r.getline(s1,501);
	r.getline(s2,501);
	memmove(s1+1,s1,strlen(s1));
	memmove(s2+1,s2,strlen(s2));	
	w<<(LCSLength()%MOD);
	r.close(); w.close();
}