#include <fstream>
#include <cstring>
using namespace std;
#define dim 505
#define M 666013

string S1,S2;
int d[dim][dim];
int ways[dim][dim];
int l[2][26];
bool used[26];

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

    fin >> S1 >> S2;

    int N1 = S1.size();
    int N2 = S2.size();

    for(int i = 0; i < N1; i++)
        for(int j = 0; j < N2; j++)
            if(S1[i] == S2[j])
                d[i][j] = d[i-1][j-1] + 1;
            else
                d[i][j] = max(d[i-1][j],d[i][j-1]);

    memset(l[0],-1,sizeof l[0]);

    int W = 0;

    /*
    for(int i = 0; i < N1; i++)
    {
        for(int j = 0; j < N2; j++)
            fout << d[i][j] << " ";
        fout << "\n";
    }
    */

    //fout << "\n";

    for(int i = 0; i < N1; i++){
        for(int j = 0; j < N2; j++){
            if(S1[i] == S2[j]){

                if(d[i][j] == 1)
                    ways[i][j] = 1;
                else{
                    for(int k = 0; k < 26; k++){
                        if(l[1][k] != -1 && l[0][k] != -1){
                            if(d[l[0][k]][l[1][k]] + 1 == d[i][j]){
                                ways[i][j] += ways[l[0][k]][l[1][k]];
                                if(ways[i][j] >= M) ways[i][j] -= M;
                            }
                        }
                    }
                }

                if(d[i][j] == d[N1-1][N2-1] && !used[S1[i]-'a']){
                    W += ways[i][j];
                    if(W >= M) W -= M;
                    used[S1[i]-'a'] = 1;
                }

            }

            //fout << ways[i][j] << " ";

            l[1][S2[j]-'a'] = j;
        }

        //fout << "\n";

        l[0][S1[i]-'a'] = i;
        memset(l[1],-1,sizeof l[1]);
    }

    fout << W << "\n";

}