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

int dp[505][505], cnt[505][505], ans, cntAns;
string a,b;

void sum(int &a, int b){
    a += b;
    if (a < 0) a += MOD;
    else if (a >= MOD) a -= MOD;
}

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

    cin >> a >> b;

    for (int j=0;j<=b.size();j++){
        cnt[0][j] = 1;
    }
    for (int i=1;i<=a.size();i++){
        for (int j=1;j<=b.size();j++){
            if (a[i-1] == b[j-1]){
                dp[i][j] = dp[i-1][j-1] + 1;
                cnt[i][j] = max(1, cnt[i-1][j-1]);
            }
            else{
                dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
                if (dp[i][j] == dp[i-1][j]) sum(cnt[i][j], cnt[i-1][j]);
                if (dp[i][j] == dp[i][j-1]) sum(cnt[i][j], cnt[i][j-1]);
                if (dp[i][j-1] == dp[i-1][j-1] && dp[i][j-1] == dp[i-1][j]) sum(cnt[i][j], -cnt[i-1][j-1]);
            }
        }
    }

    cout << cnt[a.size()][b.size()] << '\n';

    return 0;
}