#include <fstream>
#include <cstring>

using namespace std;
char s1[600], s2[600];
int sir[600][600], Nr[600][600];
void read()
{
    ifstream f("subsir.in");
    f.getline(s1+1,599);
    f.getline(s2+1,599);
}

void solve1()
{
    int x=strlen(s1+1);
    int y=strlen(s2+1);
    for(int i = 1; i <= x; ++i)
        for(int j = 1; j <= y; ++j){

            if( s1[i] == s2[j] ) sir[i][j] = sir[i-1][j-1] + 1;
                else sir[i][j] = max(sir[i-1][j], sir[i][j-1]);
        }
}

void solve2()
{
    ofstream g("subsir.out");

    int x=strlen(s1+1);
    int y=strlen(s2+1);
    for(int i = 1; i <= x; ++i)
        for(int j = 1; j <= y; ++j){

            if( i == 1 || j == 1) {Nr[i][j]=1;continue;}
            Nr[i][j]=0;
            if (s1[i] == s2[j]) Nr[i][j] = Nr[i-1][j-1];
                else
                {
                    if(sir[i][j] == sir[i-1][j]) Nr[i][j] += Nr[i-1][j];
                    if(sir[i][j] == sir[i][j-1]) Nr[i][j] += Nr[i][j-1];
                    if(sir[i][j] == sir[i-1][j-1]) Nr[i][j] = Nr[i][j] + 666013, Nr[i][j] -= Nr[i-1][j-1];
                }
            Nr[i][j]=(Nr[i][j]%666013);
        }
    g<<Nr[x][y]<<"\n";
}

int main()
{
    read();
    solve1();
    solve2();
    return 0;
}