#include<stdio.h>
#include<cstring>
#define mod 666013
using namespace std;
char a[505],b[505],x;
int d[505][505],nr[505][505],i,j,n,m;
int main()
{
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    scanf("%c",&x);
    while(x>='a'&&x<='z')
    {
        n++;
        a[n]=x;
        scanf("%c",&x);
    //    printf("%c",x);
    }
    while(x<'a'||x>'z')
    scanf("%c",&x);
    while(x>='a'&&x<='z')
    {
        m++;
        b[m]=x;
        scanf("%c",&x);
    
    }

    for(i=0;i<=n;i++){
        nr[i][0]=1;
    }
    for(j=0;j<=m;j++)
        nr[0][j]=1;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {

            if(a[i]==b[j])
            {
                d[i][j]=d[i-1][j-1]+1;
                nr[i][j]=nr[i-1][j-1];


             }
             else
             {
                 if(d[i-1][j]==d[i][j-1])
                 {
                     d[i][j]=d[i-1][j];
                     nr[i][j]=(nr[i-1][j]+nr[i][j-1])%mod;
                     if(d[i-1][j-1]==d[i][j-1])
                     {
                         nr[i][j]-=nr[i-1][j-1]-mod;
                         nr[i][j]%=mod;
                     }
                 }
                 else
                     if(d[i-1][j]>d[i][j-1])
                     {
                         d[i][j]=d[i-1][j];
                         nr[i][j]=nr[i-1][j];

                     }
                     else
                     {
                         d[i][j]=d[i][j-1];
                         nr[i][j]=nr[i][j-1];
                     }

             }
        }
    printf("%d",nr[n][m]);
    return 0;
}