#include <iostream>
#include <fstream>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#define NMAX 501

using namespace std;

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

int strlen(char *s)
{
    int i=0;
    while(s[i]!='\0')
        ++i;

    return i;
}

int main()
{
    char a[NMAX],b[NMAX];
    fin.get(a,NMAX);
    fin.get();
    fin.get(b,NMAX);
    int lcs[NMAX][NMAX]={0};
    int n=strlen(a),m=strlen(b),nr=0,mx=0;
    for(int i=1;i<=n;++i)
        {
        for(int j=1;j<=m;++j)
        {
            if(a[i-1]==b[j-1])
                {
                    lcs[i][j]=lcs[i-1][j-1]+1;
                    if(lcs[i][j]>mx)
                    {
                        mx=lcs[i][j];
                        nr=1;
                    }
                    else if(lcs[i][j]==mx && lcs[i][j]!=lcs[i][j-1] && lcs[i-1][j]!=lcs[i][j])
                        ++nr;
                }
            else
                lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1]);
            nr%=666013;
        }
        }

    fout<<nr;

    return 0;
}