#include <map>
#include <fstream>
#include <string>
#include <vector>
#include <iostream>

#define RANGE 666013
#define displayMaxSs \
for(int i=0; i<len[0]; i++)\
{\
    for(int j=0; j<len[1]; j++)\
        std::cout<<maxSs[i][j]<<' ';\
    std::cout<<'\n';\
}
#define displayFPA \
for(int i=0; i<2; i++)\
    for(char c='a'; c<='z'; c++)\
        for(int j=0; j<len[i]; j++)\
            std::cout<<"string "<<i+1<<" character\'"<<c<<"\' first after "<<j<<" is "<<firstPozAfter[i][c][j]<<'\n';

int M,len[2],maxSs[500][500];
std::vector<std::map<char, std::vector<int>>> firstPozAfter;

int countSs(int,int,int);

int main()
{
    std::fstream f("subsir.in",std::ios::in),
                g("subsir.out",std::ios::out);

    std::string ss[2];
    f>>ss[0]>>ss[1];
    len[0] = ss[0].length();
    len[1] = ss[1].length();

    firstPozAfter.resize(2);
    for(int i=0; i<2; i++)
        for(char c = 'a'; c <= 'z'; c++)
            firstPozAfter[i][c].resize(len[i]);

    for(int i=0; i<2; i++)
        for(char c = 'a'; c <= 'z'; c++)
        {
            int j=0;
            for(int k=0; k < len[i]; k++)
                if(ss[i][k] == c)
                    while(j <= k)
                    {
                        firstPozAfter[i][c][j] = k;
                        j++;
                    }
            while(j < len[i])
            {
                firstPozAfter[i][c][j] = -1;
                j++;
            }
        }

    for(int i=len[0] - 1; i >= 0; i--)
        for(int j=len[1] - 1; j >= 0; j--)
        {
            if(i == len[0] - 1)
            {
                if(j == len[1] - 1)
                    maxSs[i][j] = (ss[0][i] == ss[1][j]);

                else maxSs[i][j] = std::max(int(ss[0][i]==ss[1][j]),maxSs[i][j+1]);
            }
            else
            {
                if(j == len[1] - 1)
                    maxSs[i][j] = std::max(int(ss[0][i]==ss[1][j]),maxSs[i+1][j]);

                else maxSs[i][j] = std::max((maxSs[i+1][j+1]+1)*(ss[0][i]==ss[1][j]),
                                    std::max(maxSs[i][j+1],maxSs[i+1][j]));
            }
        }

    M = maxSs[0][0];

    int sol = countSs(0,0,M);
    g<<sol;
}

int countSs(int s1, int s2, int M)
{
    if(s1 >= len[0] || s2 >= len[1])return (M == 0);

    int sol = 0;
    for(char c = 'a'; c <= 'z'; c++)
    {
        int p1 = firstPozAfter[0][c][s1];//after(including)
        int p2 = firstPozAfter[1][c][s2];

        if(p1 == -1 || p2 == -1)continue;

        if(maxSs[p1+1][p2+1] == M-1)
            sol += countSs(p1+1, p2+1, M-1);
    }
    return sol % RANGE;
}