#include <stdio.h>
#include <cstring>
#define nmax 1024
#define max(a,b) (a>b)?a:b
using namespace std;
int n,m,c[nmax][nmax],i,j,sub[nmax],nr=1;
char a[nmax],b[nmax];

int main()
{
    FILE *f=fopen("subsir.in","r"),*g=fopen("subsir.out","w");
    fscanf(f,"%s",&a);
    fscanf(f,"%s",&b);
    n=strlen(a);strcpy(a,a+1);
    m=strlen(b);strcpy(b,b+1);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        if(a[i]==b[j])
            {
                c[i][j]=c[i-1][j-1]+1;
                if(c[i-1][j]!=c[i][j]&&c[i][j-1]!=c[i][j])
                    sub[c[i][j]]++;
            }
    else c[i][j]=max(c[i-1][j],c[i][j-1]);
    for(i=1;sub[i]!=0;i++)nr*=sub[i];
    fprintf(g,"%d\n",nr%666013);


    return 0;
}