#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[1]);
    fscanf(f,"%s",&b[1]);
    n=strlen(a+1);
    m=strlen(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;
        else c[i][j]=max(c[i-1][j],c[i][j-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])&&(c[i-1][j]!=c[i][j])&&(c[i][j-1]!=c[i][j]))sub[c[i][j]]++;

    for(i=1;sub[i]!=0;i++)
        nr*=sub[i];
    fprintf(g,"%d\n",nr%666013);


    return 0;
}