#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>

#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define ll long long
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define sz size
#define DBG(X) cerr << X << "\n";

using namespace std;

char A[512], B[512];
int dp[512][512], ways[512][512], lastA[200][512], lastB[200][512];

const int mod = 666013;

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

    gets(A + 1); gets(B + 1);
    int N = strlen(A + 1); int M = strlen(B + 1);
    A[++N] = '#'; B[++M] = '$';

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
            if (A[i] == B[j])
                dp[i][j] = 1 + dp[i - 1][j - 1];
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

    for (int i = 1; i <= N; ++i)
        for (char ch = 'a'; ch <= 'z'; ++ch)
            lastA[ch][i] = (A[i] == ch) ? i : lastA[ch][i - 1];
    for (int i = 1; i <= M; ++i)
        for (char ch = 'a'; ch <= 'z'; ++ch)
            lastB[ch][i] = (B[i] == ch) ? i : lastB[ch][i - 1];

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
            if (A[i] == B[j]) {
                for (char ch = 'a'; ch <= 'z'; ++ch) {
                    int k = lastA[ch][i - 1];
                    int l = lastB[ch][j - 1];
                    if (dp[k][l] + 1 == dp[i][j] && k && l) {
                        ways[i][j] += ways[k][l];
                        if (ways[i][j] >= mod)
                            ways[i][j] -= mod;
                    }
                }
                if (ways[i][j] == 0)
                    ways[i][j] = 1;
            }

    int res = 0;
    for (char ch = 'a'; ch <= 'z'; ++ch) {
        int k = lastA[ch][N - 1];
        int l = lastB[ch][M - 1];
        if (dp[k][l] + 1 == dp[N][M] && k && l) {
            res += ways[k][l];
            if (res >= mod)
                res = res - mod;
        }
    }

    printf("%d", res);
    return 0;
}