#include <bits/stdc++.h>

using namespace std;
ifstream in("subsir.in");
ofstream out("subsir.out");

#define MOD 666013
#define maxN 500

string a,b;
int ans[maxN+1][maxN+1],dp[maxN+1][maxN+1];

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

int main() {
	in>>a>>b;
	int n=a.size();
    int 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]);
                }
			}
		}
    }
	out<<ans[n][m]<<'\n';
}