#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

ifstream fin ("subsir.in");
ofstream fout ("subsir.out");

char s1[505] , s2[505];
int n , m;
int comun[505][505];
int dist[505][505];

int main() {
	
	fin >> (s1 + 1) >> (s2 + 1);
	n = strlen(s1 + 1);
	m = strlen(s2 + 1);
	for (int i = 0 ; i < n ; ++i) comun[0][i] = 1; 
	for (int j = 0 ; j < m ; ++j) comun[j][0] = 1;
	
	for (int i = 1 ; i <= n ; ++i)
		for(int j = 1 ; j <= m ; ++j){
			if(s1[i] = s1[j]) dist[i][j] = dist[i-1][j-1] + 1;
			else dist[i][j] = max(dist[i-1][j] , dist[i][j-1]);
		}
	
	for (int i = 1;  i <= n ; ++i){
		for(int j = 1 ; j <= m ; ++j){
			if(s1[i] == s2[j]) comun[i][j] = comun[i-1][j-1];
			else{
				int maxim = max(dist[i-1][j] , dist[i][j-1]);
				if(dist[i-1][j] == maxim) comun[i][j] += comun[i-1][j];
                if(dist[i][j-1] == maxim) comun[i][j] += comun[i][j-1];
                if(dist[i-1][j-1] == maxim) 
                    comun[i][j] -= comun[i-1][j-1]; 
			}
			comun[i][j] = comun[i][j] % 666013;
		}
	}
	
	fout << comun[n][m];
	return 0;
}