#include <fstream>
//#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
ifstream cin("subsir.in");
ofstream cout("subsir.out");
const int M=666013;
string a, b;
int ans[512][512], dp[512][512];

void add(int& x, int y){
	x+=y;
	if(x>=M) x-=M;
}
void dif(int& x, int y){
	x+=M; x-=y;
	if(x>=M) x-=M;	
}

int main(){
	cin >> a >> b; 
	int n = a.size(), m = b.size();
	a='0'+a; b='0'+b;
	for(int i=1; i<=n; ++i)
		for(int j=1; j<=m; ++j){
			if(a[i]==b[j]){
				ans[i][j]=max(1, ans[i-1][j-1]);
				dp[i][j]=1+dp[i-1][j-1];
			}
			else {
				dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
				if(dp[i][j]==dp[i-1][j])
					add(ans[i][j], ans[i-1][j]);
				if(dp[i][j]==dp[i][j-1])
					add(ans[i][j], ans[i][j-1]);
				if(dp[i][j]==dp[i-1][j-1]&&dp[i-1][j]==dp[i][j-1])
					dif(ans[i][j], ans[i-1][j-1]);
			}
		}
	cout << ans[n][m] << '\n';
}