#include <bits/stdc++.h>
#define newline '\n'
using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");
///***********************
const int NMAX = 503, MOD = 666013;
char a[NMAX], b[NMAX];
int n, m, finAns;
int dp[NMAX][NMAX];//dp[i][j]-len of longest common ss in a[1...i], b[1...j]
int lastPos[2][NMAX][NMAX];//[0][i][j] - last apparition of j in a between a[1...i]
int ans[NMAX][NMAX];//nr of common ss of max len in a[1...i],b[1...j]


void computeDP()
{
    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;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}

inline int mapping(char c)
{
    return c - 'a';
}

void computeLastPos()
{
    for (char c = 'a'; c <= 'z'; c++)
    {
        for (int i = 1; i <= n; i++)
            if (a[i] == c)
                lastPos[0][i][mapping(c)] = i;
            else
                lastPos[0][i][mapping(c)] = lastPos[0][i - 1][mapping(c)];
        for (int j = 1; j <= m; j++)
            if (b[j] == c)
                lastPos[1][j][mapping(c)] = j;
            else
                lastPos[1][j][mapping(c)] = lastPos[1][j - 1][mapping(c)];
    }
}

void computeAns()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i] == b[j])
            {
                if (dp[i][j] == 1)
                {
                    ans[i][j] = 1;
                    continue;
                }
                for (char c = 'a'; c <= 'z'; c++)
                {
                    int ii = lastPos[0][i - 1][mapping(c)];
                    int jj = lastPos[1][j - 1][mapping(c)];
                    if (!ii || !jj)
                        continue;
                    if (dp[i][j] == dp[ii][jj] + 1)
                        ans[i][j] = (ans[i][j] + ans[ii][jj]) % MOD;
                }
            }
    for (char c = 'a'; c <= 'z'; c++)
    {
        int ii = lastPos[0][n][mapping(c)];
        int jj = lastPos[1][m][mapping(c)];
        if (!ii || !jj)
            continue;
        if (dp[ii][jj] == dp[n][m])
            finAns = (finAns + ans[ii][jj]) % MOD;
    }
}

int main()
{
    fin >> (a + 1) >> (b + 1);
    n = strlen(a + 1);
    m = strlen(b + 1);
    computeDP();
    computeLastPos();
    computeAns();//cerr<<lastPos[0][n][mapping('b')];
    fout << finAns << newline;
    fout.close();
    return 0;
}