#include <fstream>
#include <cstring>

#define MOD 666013
#define DIM 510

using namespace std;

ifstream f ("subsir.in");
ofstream g ("subsir.out");

int mat[DIM][DIM] , dp[DIM][DIM];
int n , m;

char a[DIM] , b[DIM];

int main() {
    f >> a + 1 >> b + 1;

    int n = strlen(a + 1);
    int m = strlen(b + 1);

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i] == b[j]) {
                mat[i][j] = mat[i - 1][j - 1] + 1;
            }

            else {
                mat[i][j] = max(mat[i - 1][j] , mat[i][j - 1]);
            }
        }
    }

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

    for (int i = 0; i <= m; ++i) {
        dp[0][i] = 1;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i] == b[j]) {
                dp[i][j] = dp[i - 1][j - 1];
                dp[i][j] %= MOD;
            }

            else {
                if (mat[i][j] == mat[i - 1][j]) {
                    dp[i][j] += dp[i - 1][j];
                }

                if (mat[i][j] == mat[i][j - 1]) {
                    dp[i][j] += dp[i][j - 1];
                }

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

                dp[i][j] %= MOD;
            }
        }
    }

    g << dp[n][m];
    return 0;
}