#include <stdio.h>
int a[501],b[501],c[501];
int m[501][501];
int n,s,x;
int max (int a,int b)
{
    return a>b?a:b;
}
void read ()
{
    char ch;
    while (scanf ("%c",&ch)!='\n')
        a[++n]=ch-'a';
    while (scanf ("%c",&ch)!=EOF)
        b[++s]=ch-'a';
}
void solve ()
{
    int i,j;
    for (i=1; i<=n; ++i)
        for (j=1; j<=s; ++j)
            if (a[i]==b[j])
                m[i][j]=m[i-1][j-1]+1;
            else
                m[i][j]=max (m[i-1][j],m[i][j-1]);
    /*for (i=n, j=s; i; )
    {
        if (a[i]==b[j])
        {
            c[++x]=a[i];
            --i;
            --j;
        }
        else if (m[i-1][j]<m[i][j-1])  
            --j;  
        else  
            --i;  
    }*/
    int mula=0;
    for (i=1; i<=n; ++i)
        for (j=1; j<=s; ++j)
            if (m[i][j]==m[n][s])
            {
                ++mula;
                mula%=666013;
            }
    printf ("%d",mula);
}
int main ()
{
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    read ();
    solve ();
    return 0;
}