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

#define MOD 666013

/**
 * @brief dp[i][j] - lungimea celui mai lung subsir comun
 * format cu elementele din vectorii v[1..i] si w[1..j]
 * 
 * count[i][j] - numarul de subsiruri comune distincte de lungime
 * maxima format cu elementele din vectorii v[1..i] si w[1..j]
 */
class Task {
 public:
    void solve() {
        read_input();
        print_output(get_result());
    }

 private:
    string v, w;

    void read_input() {
        ifstream fin("subsir.in");
        fin.tie(0);

        fin >> v >> w;
        fin.close();
    }

    int get_result() {
        int n = v.size();
        int m = w.size();

        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        vector<vector<int>> count(n + 1, vector<int>(m + 1, 0));

        for (int i = 0; i <= n; ++i) {
            count[i][0] = 1;
        }

        for (int j = 0; j <= m; ++j) {
            count[0][j] = 1;
        }

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (v[i - 1] == w[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    count[i][j] = count[i - 1][j - 1];
                
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

                    if (dp[i][j] == dp[i - 1][j]) {
                        count[i][j] = (count[i][j] + count[i - 1][j]) % MOD;
                    }

                    if (dp[i][j] == dp[i][j - 1]) {
                        count[i][j] = (count[i][j] + count[i][j - 1]) % MOD;
                    }

                    if (dp[i][j] == dp[i - 1][j] && dp[i][j] == dp[i][j - 1]) {
                        count[i][j] = (count[i][j] - count[i - 1][j - 1]) % MOD;
                    }
                }
            }
        }

        return count[n][m];
    }

    void print_output(int result) {
        ofstream fout("subsir.out");
        fout.tie(0);

        fout << result << "\n";
        fout.close();
    }
};

int main() {
    ios::sync_with_stdio(false);
    auto* task = new (nothrow) Task();

    if (!task) {
        cerr << "new failed\n";
        return -1;
    }

    task->solve();
    delete task;

    return 0;
}