#include <fstream>
#include <string>

using namespace std;

int N, M;
string A, B;

const int MOD = 666013;
const int NMAX = 500 + 5;

int nextA[26][NMAX];
int nextB[26][NMAX];

int dp[NMAX][NMAX];
int cnt[NMAX][NMAX];

int main()
{
    ifstream cin("subsir.in");
    ofstream cout("subsir.out");

    cin >> A >> B;

    A += "z";
    B += "z";
    N = A.size();
    M = B.size();
    A = " " + A;
    B = " " + B;

    for (int i = 1; i <= N; ++ i) {
        for (int j = 0; j < 26; ++ j)
            nextA[j][i] = nextA[j][i - 1];
        if (i >= 2)
            nextA[A[i - 1] - 'a'][i] = i - 1;
    }
    for (int i = 1; i <= M; ++ i) {
        for (int j = 0; j < 26; ++ j)
            nextB[j][i] = nextB[j][i - 1];
        if (i >= 2)
            nextB[B[i - 1] - 'a'][i] = i - 1;
    }

    for (int i = 1; i <= N; ++ i)
        for (int j = 1; j <= M; ++ j)
            if (A[i] == B[j]) {
                for (int ch = 0; ch < 26; ++ ch)
                    if (nextA[ch][i] && nextB[ch][j])
                        dp[i][j] = max(dp[i][j], dp[nextA[ch][i]][nextB[ch][j]]);

                for (int ch = 0; ch < 26; ++ ch)
                    if (nextA[ch][i] && nextB[ch][j])
                        if (dp[i][j] == dp[nextA[ch][i]][nextB[ch][j]]) {
                            cnt[i][j] += cnt[nextA[ch][i]][nextB[ch][j]];
                            if (cnt[i][j] >= MOD)
                                cnt[i][j] -= MOD;
                        }
                ++ dp[i][j];
                if (dp[i][j] == 1)
                    cnt[i][j] = 1;
            }

    cout << cnt[N][M] << '\n';
    return 0;
}