#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const char iname[]="subsir.in";
const char oname[]="subsir.out";
const int maxn=507;
const int mod=666013;

int lcs[maxn][maxn],nr[maxn][maxn],i,j,n,m,lasta[26][maxn],lastb[26][maxn],k;

char a[maxn],b[maxn];

int main()
{
    freopen(iname,"r",stdin);
    freopen(oname,"w",stdout);
    fgets(a+1,sizeof(a),stdin);
    fgets(b+1,sizeof(b),stdin);
    n=strlen(a+1);
    m=strlen(b+1);
    if(a[n]=='\n')
        a[n--]=0;
    if(b[m]=='\n')
        b[m--]=0;

    a[++n]='a';
    b[++m]='a';
    for(i=1;i<=n;++i)
        lcs[i][0]=0,nr[i][0]=1;
    for(i=1;i<=m;++i)
        lcs[0][i]=0,nr[0][i]=1;
    lcs[0][0]=0;
    nr[0][0]=1;
    for(i=1;i<=n;lasta[a[i]-'a'][i]=i,++i)
        for(j=0;j<26;++j)
            lasta[j][i]=lasta[j][i-1];
    for(i=1;i<=m;lastb[b[i]-'a'][i]=i,++i)
        for(j=0;j<26;++j)
            lastb[j][i]=lastb[j][i-1];

    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            if(a[i]!=b[j])
                lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1]);
            else
            {
                lcs[i][j]=lcs[i-1][j-1]+1;
                if(lcs[i][j]>1)
                    for(k=0;k<26;++k)
                        if(lcs[lasta[k][i-1]][lastb[k][j-1]]==lcs[i][j]-1)
                        {
                            nr[i][j]+=nr[lasta[k][i-1]][lastb[k][j-1]];
                            if(nr[i][j]>mod)
                                nr[i][j]-=mod;
                        }
                        else;
                else
                    nr[i][j]=1;
            }

    printf("%d\n",nr[n][m]);

    fclose(stdin);
    fclose(stdout);

    return 0;
}