#include <fstream>
#include <cstring>
using namespace std;
#define NMax 505
#define MOD 66013
char s1[NMax],s2[NMax];
int a[NMax], b[NMax];
int l[NMax][NMax], d[NMax][NMax];
int n,m,i,j;
int main()
{
    ifstream f("subsir.in");
    ofstream g("subsir.out");
    f.getline(s1,505);
    f.getline(s2,505);
    n=strlen(s1);
    m=strlen(s2);
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
        if(s1[i]==s2[j])
           l[i][j]=l[i-1][j-1]+1;
         else l[i][j]=max(l[i-1][j],l[i][j-1]);
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
           if(i==0||j==0) d[i][j]=1;
             else if(s1[i]==s2[j]) d[i][j]=d[i-1][j-1];
             else {  if(l[i-1][j]==l[i][j])
                         d[i][j]=(d[i][j]+d[i-1][j])%MOD;
                     if(l[i][j-1]==l[i][j])
                           d[i][j]=(d[i][j]+d[i][j-1])%MOD;
                     if(l[i-1][j-1]==l[i][j])
                            d[i][j]=(d[i][j]-d[i-1][j-1]+MOD)%MOD;




             }
     g<<d[n-1][m-1];

    return 0;
}