#include<fstream>
#include<string.h>
#define mod 666013
using namespace std;
ifstream f("subsir.in");
ofstream g("subsir.out");
char S[502],P[502];
int i,n,j,m;
int D[502][502],No[502][502];
inline void sub(){
	for(i=0;i<n;i++)
		No[i][0]=1;
	for(i=0;i<m;i++)
		No[0][i]=1;
	
	for(i=0;i<n;i++){
		
		for(j=0;j<m;j++){
			
			if(S[i]==P[j]){
				D[i+1][j+1]=1+D[i][j];
				No[i+1][j+1]=No[i][j]%mod;
			}
			else{
				if(D[i][j+1]>D[i+1][j]){
					D[i+1][j+1]=D[i][j+1];
					No[i+1][j+1]=(No[i][j+1])%mod;
				}
				else{
					if(D[i+1][j]>D[i][j+1]){
						D[i+1][j+1]=D[i+1][j];
						No[i+1][j+1]=(No[i+1][j])%mod;
					}
					else{
						if(D[i+1][j]==D[i][j+1]){
							D[i+1][j+1]=D[i][j+1];
							No[i+1][j+1]=(No[i][j+1]+No[i+1][j])%mod;
						}
					}
				}
			}
		}
	}
}
int main (){
	f.getline(S,502);
	f.getline(P,502);
	n=strlen(S);
	m=strlen(P);
	sub();
	g<<No[n][m]%mod;
	return 0;
}