#include <bits/stdc++.h>

using namespace std;

inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}

const int MOD = 666013;

char a[502], b[501];

int dp1[501][501], dp2[501][501];
int N, M;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    Open("subsir");

    cin >> (a + 1) >> (b + 1);
    N = strlen(a + 1), M = strlen(b + 1);

    for(int i = 0;i <= N;i++)
        for(int j = 0;j <= M;j++) {
            if(i == 0 || j == 0) {
                dp1[i][j] = 0, dp2[i][j] = 1;
            }else if(a[i] == b[j]) {
                dp1[i][j] = (dp1[i - 1][j - 1] + 1) % MOD;
                dp2[i][j] = dp2[i - 1][j - 1]; 
            } else {
                if(dp1[i - 1][j] > dp1[i][j - 1]) {
                    dp1[i][j] = dp1[i - 1][j];
                    dp2[i][j] = dp2[i - 1][j];
                } else if(dp1[i - 1][j] < dp1[i][j - 1]){
                    dp1[i][j] = dp1[i][j - 1];
                    dp2[i][j] = dp2[i][j - 1];
                } else {
                    dp1[i][j] = dp1[i - 1][j];
                    dp2[i][j] = (dp2[i][j - 1] + dp2[i - 1][j]) % MOD;
                    if(dp1[i - 1][j] == dp1[i - 1][j - 1])
                        dp2[i][j] = (dp2[i][j] - dp2[i - 1][j - 1] + MOD) % MOD;
                }
            }
        }

    cout << dp2[N][M];

    return 0;
}