#include<fstream>
#include<cstring>
#define DN 505
#define M 66013
using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");
int n,m,dp1[DN][DN],dp2[DN][DN];
char a[DN],b[DN];
int main()
{
    fin.getline(a+1,DN);
    fin.getline(b+1,DN);
    n=strlen(a+1);
    m=strlen(b+1);
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
        {
            if(i==0||j==0)
            {
                dp1[i][j]=0;
                dp2[i][j]=1;
                continue;
            }
            if(dp1[i-1][j]>dp1[i][j-1])
            {
                dp1[i][j]=dp1[i-1][j];
                dp2[i][j]=dp2[i-1][j];
            }
            else
                if(dp1[i][j-1]>dp1[i-1][j])
                {
                    dp1[i][j]=dp1[i][j-1];
                    dp2[i][j]=dp2[i][j-1];
                }
                else
                    if(dp1[i-1][j])
                        dp2[i][j]=(dp2[i][j-1]+dp2[i-1][j])%M;
                    else
                        dp2[i][j]=1;
            if(a[i]==b[j])
            {
                if(dp1[i-1][j-1]+1>dp1[i][j])
                {
                    dp1[i][j]=dp1[i-1][j-1]+1;
                    dp2[i][j]=dp2[i-1][j-1];
                }
                else
                    if(dp1[i-1][j-1]+1==dp1[i][j])
                        dp2[i][j]=(dp2[i][j]+dp2[i-1][j-1])%M;
            }
        }
    fout<<dp2[n][m];
}