#include <cstdio>
#include <cstring>

using namespace std;

char sir1[502],sir2[502];
int d[502][502],d1[502][502];
const int mod=666013;

int main()
{
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    int l1,l2;
    gets(sir1+1);
    gets(sir2+1);
    l1=strlen(sir1+1);
    l2=strlen(sir2+1);
    for(int i=0;i<=l1;i++) d1[i][0]=1;
    for(int i=0;i<=l2;i++) d1[0][i]=1;
    for(int i=1;i<=l1;i++)
        for(int j=1;j<=l2;j++)
            if(sir1[i]==sir2[j])
            {
                d[i][j]=d[i-1][j-1]+1;
                d1[i][j]=d1[i-1][j-1];
            }
            else
            {
                if(d[i][j-1]>d[i-1][j]) {d[i][j]=d[i][j-1];d1[i][j]=d1[i][j-1];}
                else if(d[i-1][j]>d[i][j-1]) {d[i][j]=d[i-1][j];d1[i][j]=d1[i-1][j];}
                else
                {
                    d[i][j]=d[i-1][j];
                    d1[i][j]=(d1[i-1][j]+d1[i][j-1])%mod;
                    if(d[i-1][j-1]==d[i-1][j]) d1[i][j]=(d1[i][j]-d1[i-1][j-1]+mod)%mod;
                }
            }
    printf("%d",d1[l1][l2]);
    return 0;
}