#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream f("subsir.in");
ofstream g("subsir.out");

char a[512],b[512];
int i,j,n,m,k,s,max1=0,d[625][625],pos,sol=0;
int main()
{
    f>>a;
    f>>b;
    n=strlen(a);
    m=strlen(b);
    for(i=0;i<n;i++)
    for(j=0;j<m;j++)
    {
        if(a[i]==b[j])
            d[i][j]=d[i-1][j-1]+1;
        else
            d[i][j]=max(d[i-1][j],d[i][j-1]);
        max1=max(max1,d[i][j]);
    }
    for(i=n-1;i>=0;i--)
    for(j=0;j<m;j++)
    {
        if(pos>=m)
        {
            g<<sol%666013;
            return 0;
        }
        if(d[i][j]==max1)
        {
            sol++;
            pos=j+1;
            break;
        }
    }
}