#include <fstream>
#include <cstring>

using namespace std;
const int MOD = 666013;

int DP[505][505], N, M, nr[505][505], lastA[30], lastB[30], sol;
char a[505], b[505];

ifstream f("subsir.in");
ofstream g("subsir.out");

int main()
{
    f >> a >> b;
    N = strlen(a);
    M = strlen(b);
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            if(a[i - 1] == b[j - 1])
            {
                DP[i][j] = DP[i - 1][j - 1] + 1;
                if(DP[i][j] == 1)
                    nr[i][j] = 1;
                else
                {
                    for (int k = 0; k <= 26; k++)
                    {
                        int lin, col;
                        lin = lastA[k];
                        col = lastB[k];
                        if(DP[lin][col] + 1 == DP[i][j])
                            nr[i][j] = (nr[lin][col] + nr[i][j]) % MOD;
                    }
                }
            }
            else
                DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);
            if(i < N)
                lastB[b[j - 1] - 'a'] = j;
        }
        lastA[a[i - 1] - 'a'] = i;
    }
    for (int i = 0; i <= 26; i++)
    {
        int lin, col;
        lin = lastA[i];
        col = lastB[i];
        if(DP[lin][col] == DP[N][M])
            sol = (sol + nr[lin][col]) % MOD;
    }
    g << sol;
    f.close();
    g.close();
    return 0;
}