#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,n,m;

int LCSLength()
{
	 for(i=0; i<=m; i++)
        nr[0][i]=1;
    for(i=0; i<=n; i++)
        nr[i][0]=1;
	
	for(i=1;i<=n;i++)
		for(j=1;j<=m;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] = c[i-1][j];
					nr[i][j] = nr[i-1][j];
				}
				else
					if(c[i-1][j]<c[i][j-1])
					{
						c[i][j]=c[i][j-1];
						nr[i][j] = nr[i][j-1];
					}
				else
				{
					c[i][j] = c[i-1][j];
					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[n][m];
}				


int main()
{
	r.getline(s1+1,501);
	r.getline(s2+1,501);	
	n=strlen(s1+1); m=strlen(s2+1);
	w<<(LCSLength()%MOD);
	r.close(); w.close();
	return 0;
}