#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 500, mod = 666013;

int dp[nmax + 5][nmax + 5], first[2][nmax + 5][30], nr[nmax + 5][nmax + 5];
string a, b;

int main()
{
    fin >> a >> b;
    for (int ch = 'a'; ch <= 'z'; ++ch)
    {
        first[0][a.size()][ch - 'a'] = a.size() + 1;
        for (int i = a.size() - 1; i >= 0; --i)
        {
            if (a[i] == ch) first[0][i][ch - 'a'] = i;
            else first[0][i][ch - 'a'] = first[0][i + 1][ch - 'a'];
        }
        first[1][b.size()][ch - 'a'] = b.size() + 1;
        for (int i = b.size() - 1; i >= 0; --i)
        {
            if (b[i] == ch) first[1][i][ch - 'a'] = i;
            else first[1][i][ch - 'a'] = first[1][i + 1][ch - 'a'];
        }
    }
    for (int i = a.size() - 1; i >= 0; --i)
    {
        for (int j = b.size() - 1; j >= 0; --j)
        {
            if (a[i] == b[j])
            {
                dp[i][j] = 1 + dp[i + 1][j + 1];
                if (dp[i][j] == 1)
                {
                    nr[i][j] = 1;
                    continue;
                }
                for (char ch = 'a'; ch <= 'z'; ++ch)
                {
                    int ii = first[0][i + 1][ch - 'a'];
                    int jj = first[1][j + 1][ch - 'a'];
                    if (ii > a.size() || jj > b.size()) continue;
                    if (dp[ii][jj] == dp[i][j] - 1) nr[i][j]  = (nr[i][j] + nr[ii][jj]) % mod;
                }
            }
            else
            {
                dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]);
            }
        }
    }
    int ans = 0;
    for (char ch = 'a'; ch <= 'z'; ++ch)
    {
        int i = first[0][0][ch - 'a'];
        int j = first[1][0][ch - 'a'];
        if (i > a.size() || j > b.size()) continue;
        if (dp[i][j] == dp[0][0]) (ans = ans + nr[i][j]) % mod;
    }
    fout << ans;
    fin.close();
    fout.close();
    return 0;
}