#include <bits/stdc++.h>

std::ifstream fin("subsir.in");
std::ofstream fout("subsir.out");

const int SIZE = 5e2 + 5;
const int mod = 666013;

int n, m;
char a[SIZE], b[SIZE];
int dp[SIZE][SIZE], ans[SIZE][SIZE];


int64_t max(std::vector<int64_t> v){ return *std::max_element(v.begin(), v.end()); }

int64_t min(std::vector<int64_t> v){ return *std::min_element(v.begin(), v.end()); }

int main() 
{
    fin.getline(a + 1, SIZE);
    fin.getline(b + 1, SIZE);

    n = strlen(a + 1);
    m = strlen(b + 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] + 1 % mod;
                ans[i][j] = max({1, ans[i - 1][j - 1]}) % mod;
            }
            else
            {
                dp[i][j] = max({dp[i][j - 1], dp[i - 1][j]});

                if(dp[i][j - 1] > dp[i - 1][j])
                    ans[i][j] = ans[i][j - 1];

                if(dp[i - 1][j] > dp[i][j - 1])
                    ans[i][j] = ans[i - 1][j];

                if(dp[i][j] == dp[i - 1][j] && dp[i][j] == dp[i][j - 1])
                {
                    ans[i][j] = (ans[i - 1][j] + ans[i][j - 1]) % mod;
                    // evitam dubla numarare
                    if(dp[i - 1][j - 1] == dp[i - 1][j])
                        ans[i][j] = (ans[i][j] - ans[i - 1][j - 1] + mod) % mod;
                }
            }
    
    fout << ans[n][m];
    
    return 0;
}