#include <cstring>
#include <fstream>

using namespace std;

const int NMax = 512, MOD = 666013;
int n, m;
char a[NMax], b[NMax];
int best[NMax][NMax], dp[NMax][NMax], lasta[NMax][27], lastb[NMax][27];
int ans;

int main()
{
    ifstream f ("subsir.in");
    f>>(a+1);
    f>>(b+1);
    n = strlen(a+1), m = strlen(b+1);
    f.close();

    for (int i = 1; i<=n; ++i)
        for (int j = 0; j < 26; ++j)
            if (a[i] == (char)(j + 'a')) lasta[i][j] = i;
            else lasta[i][j] = lasta[i-1][j];
    for (int i = 1; i<=m; ++i)
        for (int j = 0; j < 26; ++j)
            if (b[i] == (char)(j + 'a')) lastb[i][j] = i;
            else lastb[i][j] = lastb[i-1][j];

    for (int i = 1; i<=n; ++i)
        for (int j = 1; j<=m; ++j)
            if (a[i] == b[j])
            {
                best[i][j] = best[i-1][j-1] + 1;
                if (best[i][j] == 1)
                    dp[i][j] = 1;
            }
            else
                best[i][j] = max(best[i-1][j], best[i][j-1]);

    for (int i = 1; i<=n; ++i)
        for (int j = 1; j<=m; ++j)
            if (a[i] == b[j])
            {
                for (int k = 0; k<26; ++k)
                {
                    int poza = lasta[i-1][k], pozb = lastb[j-1][k];
                    if (best[i][j] == best[poza][pozb] + 1)
                    {
                        dp[i][j] += dp[poza][pozb];
                        dp[i][j] = dp[i][j] >= MOD ? dp[i][j] - MOD : dp[i][j];
                    }
                }
                if (best[i][j] == best[n][m])
                    if (lasta[n][a[i] - 'a'] == i && lastb[m][b[j] - 'a'] == j)
                    {
                        ans += dp[i][j];
                        ans = ans >= MOD ? ans - MOD : ans;
                    }
            }
    ofstream g("subsir.out");
    g<<ans<<"\n";
    g.close();
    return 0;
}