#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");
#define nmax 502
#define mod 66013
char a[nmax], b[nmax];
int lg[nmax][nmax], nr[nmax][nmax], n, m;
int main()
{
    int i, j;
    fin>>a>>b;
    fin.close();
    n=strlen(a); m=strlen(b);
    for(i=1; i<=n; i++)
        nr[i][0]=1;
    for(i=1; i<=m; i++)
        nr[0][i]=1;
    nr[0][0]=1;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            if(a[i-1]==b[j-1])
            {
                lg[i][j]=1+lg[i-1][j-1];
                nr[i][j]=nr[i-1][j-1];
            }
            else if(lg[i-1][j]==lg[i][j-1])
            {
                lg[i][j]=lg[i-1][j];
                nr[i][j]=(nr[i-1][j]+nr[i][j-1])%mod;
                if(lg[i-1][j]==lg[i-1][j-1])
                    nr[i][j]=(nr[i][j]+mod-nr[i-1][j-1])%mod;
            }
            else if(lg[i-1][j]>lg[i][j-1])
            {
                lg[i][j]=lg[i-1][j];
                nr[i][j]=nr[i-1][j];
            }
            else if(lg[i][j-1]>lg[i-1][j])
            {
                lg[i][j]=lg[i][j-1];
                nr[i][j]=nr[i][j-1];
            }
    fout<<nr[n][m]<<'\n';
    fout.close();
    return 0;
}