#include <stdio.h>
#include <string.h>
using namespace std;

FILE *fin=fopen("subsir.in","r");
FILE *fout=fopen("subsir.out","w");
int l[501][501],nr[501][501];
char a[501],b[501];
int main()
{

    fscanf(fin,"%s\n",&a);
    fscanf(fin,"%s\n",&b);
    int n=strlen(a),m=strlen(b);
    int i,j;
    for(i=0; i<=m; i++)
        nr[0][i]=1;
    for(i=0; i<=n; i++)
        nr[i][0]=1;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            if(a[i]==b[j])
            {
                l[i][j]=l[i-1][j-1]+1;
                nr[i][j]=nr[i-1][j-1];
            }
            else if(l[i-1][j]>l[i][j-1])
            {
                l[i][j]=l[i-1][j];
                nr[i][j]=nr[i-1][j];
            }
            else if(l[i][j-1]>l[i-1][j])
            {
                l[i][j]=l[i][j-1];
                nr[i][j]=nr[i][j-1];
            }
            else
            {
                l[i][j]=l[i-1][j];
                nr[i][j]=(nr[i][j-1]+nr[i-1][j])%666013;
                if(l[i-1][j-1]==l[i-1][j]) nr[i][j]=((nr[i][j]-nr[i-1][j-1])+666013)%666013;
            }
    fprintf(fout,"%d",nr[n][m]);
    return 0;
}