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