#include <bits/stdc++.h>

using namespace std;
#define int long long int
const int mod = 666013, NMAX = 508;

int dp[NMAX][NMAX], nr[NMAX][NMAX];

string a, b;

signed main()
{
    freopen("subsir.in", "r", stdin);
    freopen("subsir.out", "w", stdout);

    cin >> a >> b;
    a = "$" + a;
    b = "$" + b;
    for (int i = 1; i < a.size(); i++) {
        for (int j = 1; j < b.size(); j++) {
            if (a[i] == b[j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                if (nr[i - 1][j - 1] == 0)
                    nr[i][j] = 1;
                else
                    nr[i][j] = nr[i - 1][j - 1];
            }
            else {
                if (dp[i - 1][j] > dp[i][j - 1]) {
                    dp[i][j] = dp[i - 1][j];
                    nr[i][j] += nr[i - 1][j];
                    nr[i][j] %= mod;
                }
                else if (dp[i][j - 1] > dp[i-1][j]) {
                    dp[i][j] = dp[i][j - 1];
                    nr[i][j] = nr[i][j - 1];
                    nr[i][j] %= mod;
                }
                else {
                    dp[i][j] = dp[i - 1][j];
                    nr[i][j] += nr[i - 1][j] + nr[i][j - 1];
                    nr[i][j] %= mod;
                    if (dp[i][j - 1] == dp[i - 1][j - 1])
                        nr[i][j] -= nr[i - 1][j - 1];
                    while (nr[i][j] < 0)
                        nr[i][j] += mod;
                    nr[i][j] %= mod;
                }
            }
        }
    }
    cout << nr[a.size()-1][b.size()-1];
    return 0;
}