#include <iostream>
#include <set>
#include <vector>
#include <iomanip>
#include <fstream>
#include <algorithm>
using namespace std;

string a, b;
int dp[505][505];
const int mod = 666013;
int lu[510][510];
ifstream fin("subsir.in");
ofstream fout("subsir.out");


void read() {
    fin >> a >> b;
    int n = a.size();
    int m = b.size();
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(a[i - 1] == b[j - 1]) {
                lu[i][j] = lu[i - 1][j - 1] + 1;
                if((i - 1) && (j - 1)) {
                    if(dp[i - 1][j -  1] == 0) {
                        dp[i][j] = 1;
                        lu[i][j] = 1;
                    } else {
                        dp[i][j] = dp[i - 1][j - 1];
                        lu[i][j] = 1 + lu[i - 1][j - 1];
                    }
                } else {
                    dp[i][j] = 1;
                }
            } else {
                int ok = 0;
                lu[i][j] = max(lu[i - 1][j], lu[i][j - 1]);
                if(lu[i - 1][j] == lu[i][j]) {
                    ok++;
                    dp[i][j] = (dp[i - 1][j] + dp[i][j]) % mod;
                }
                if(lu[i][j - 1] == lu[i][j]) {
                    ok++;
                    dp[i][j] = (dp[i][j] + dp[i][j - 1]) % mod;
                }
                if(lu[i - 1][j - 1] == lu[i][j] && ok == 2) {
                    dp[i][j] = (dp[i][j] - dp[i - 1][j - 1] + mod) % mod;
                }
            }
        }
    }

    cout << dp[n][m];
}

int main() {
    read();
    fout.close();
    fin.close();
    return 0;
}