#include <stdio.h>
#include <string.h>

#define maxS 505
#define max(a,b) (a<b?b:a)
#define mod 666013

char A[maxS];
char B[maxS];
int d[maxS][maxS];
int cnt[maxS][maxS];
int count[maxS];

int main()
{
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);

    fgets(A+1,maxS,stdin);
    fgets(B+1,maxS,stdin);

    int M=strlen(A+1);
    int N=strlen(B+1);

    for(int i=0;i<M;++i) cnt[i][0]=1;
    for(int j=0;j<N;++j) cnt[0][j]=1;

    for(int i=1;i<M;++i)
        for(int j=1;j<N;++j)
        {
            if(A[i]==B[j])
            {
                d[i][j]=d[i-1][j-1]+1;
                cnt[i][j]=cnt[i-1][j-1];
                continue;
            }

            d[i][j]=max(d[i-1][j],d[i][j-1]);

            if(d[i-1][j]>d[i][j-1])
            {
                cnt[i][j]=cnt[i-1][j];
                continue;
            }
            else
            if(d[i-1][j]<d[i][j-1])
            {
                cnt[i][j]=cnt[i][j-1];
                continue;
            }

            cnt[i][j]=(cnt[i-1][j]+cnt[i][j-1])%mod;
            if(d[i][j-1]==d[i-1][j-1])
                cnt[i][j]=(cnt[i][j]+mod-cnt[i-1][j-1])%mod;
        }

    printf("%d\n",cnt[M-1][N-1]);

    return 0;
}