#include <bits/stdc++.h>
using namespace std;

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

#define cin fin
#define cout fout
#define mod 666013

int dp[501][501];
int ans[501][501];
char a[501], b[501];
int n, m;

int main() {

    cin >> a >> b;
    n = strlen(a), m = strlen(b);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if (a[i-1]==b[j-1]) {
                dp[i][j] = dp[i-1][j-1]+1;
                if (ans[i-1][j-1]>0) {
                    ans[i][j]=ans[i-1][j-1];
                }else {
                    ans[i][j]=1;
                }
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                if (dp[i-1][j]>dp[i][j-1]) {
                    ans[i][j] = (ans[i][j]+ans[i-1][j])%mod;
                } else if (dp[i-1][j]<dp[i][j-1]) {
                    ans[i][j] = (ans[i][j]+ans[i][j-1])%mod;
                } else {
                    ans[i][j] = (ans[i][j]+ans[i][j-1]+ans[i-1][j])%mod;
                    if (dp[i-1][j-1]==dp[i][j]) {
                        ans[i][j] = (ans[i][j]-ans[i-1][j-1]+mod)%mod;
                    }
                }
            }
        }
    }
    cout << ans[n][m];
	return 0;
}