#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];
int main()
{
    char a[501],b[501];
    fscanf(fin,"%s\n",&a);
    fscanf(fin,"%s\n",&b);
    int n=strlen(a),m=strlen(b);
    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;
}