#include <stdio.h>

#define Nmax 512
#define MOD 666013

char a[Nmax], b[Nmax];
int best[Nmax][Nmax], nr[Nmax][Nmax], n,m;

void cit()
{
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);    
    
    fgets(a+1,Nmax,stdin);
    fgets(b+1,Nmax,stdin);    
    
    while (a[++n]!='\n'); --n;
    while (b[++m]!='\n'); --m;    
}

void afis()
{    
    printf("%d\n", nr[n][m]);        
}

void calc()
{
//    for (int i=1;i<=n;++i)  nr[i][0] = 1;
//    for (int j=1;j<=m;++j)  nr[0][j] = 1;
    
    for (int i=1;i<=n;++i)
    for (int j=1;j<=m;++j)
    {   
        if (a[i] == b[j]) 
        {
            best[i][j] = best[i-1][j-1] + 1;
            nr[i][j] = nr[i-1][j-1];
            if (best[i][j] == 1 && nr[i][j] == 0) nr[i][j] = 1;
        }
        else
        {
            if (best[i][j-1] == best[i][j])
            nr[i][j] = (nr[i][j]+nr[i][j-1])%MOD;
            if (best[i][j-1] > best[i][j])
            {
                best[i][j] = best[i][j-1];
                nr[i][j] = nr[i][j-1];
            }
            if (best[i-1][j] == best[i][j])
            nr[i][j] = (nr[i][j]+nr[i-1][j])%MOD;
            if (best[i-1][j] > best[i][j])
            {
                best[i][j] = best[i-1][j];
                nr[i][j] = nr[i-1][j];
            }
        }
        nr[i][j] %= MOD;        
    }
/*    
    for (int i=1;i<=n;++i)
    {
        for (int j=1;j<=m;++j)
        printf("%d ", nr[i][j]);
        printf("\n");
    }    */
}
void solve()
{
    cit();
    calc();
    afis();    
}

int main()
{
    solve();
    
    return 0;    
}