#include<bits/stdc++.h>
#define MOD 666013
using namespace std;
char s1[505],s2[505];
int n,m,V[505][505],W[505][505],d[505][505],s[505][505],pa,pb;
inline int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    scanf("%s",&s1);
    scanf("\n");
    scanf("%s",&s2);
    n=strlen(s1);
    m=strlen(s2);
    for(int i=(n-1);i>=0;i--)
    {
        s1[i+1]=s1[i];
    }
    for(int j=(m-1);j>=0;j--)
    {
        s2[j+1]=s2[j];
    }
    for(int k='a';k<='z';k++)
    for(int i=1;i<n;i++)
    {
        if (s1[i]==k)
        {
            V[k][i+1]=i;
        }
            else V[k][i+1]=V[k][i];
    }
     for(int k='a';k<='z';k++)
    for(int i=1;i<m;i++)
    {
        if (s2[i]==k)
        {
            W[k][i+1]=i;
        }
            else W[k][i+1]=W[k][i];
    }
    s[1][1]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(s1[i]==s2[j])
            {
               d[i][j]=d[i-1][j-1]+1;
            }
                else
            d[i][j]=max(d[i-1][j],d[i][j-1]);
            if (d[i][j]==1) s[i][j]=1;
                else
            {
                for(int k='a';k<='z';k++)
                {
                    pa=V[k][i];
                    pb=W[k][j];
                    if (d[i][j]==(d[pa][pb]+1))
                    {
                        s[i][j]=(s[i][j]+s[pa][pb])%MOD;
                    }
                }
            }
        }
    }
    printf("%d\n",s[n][m]);
    return 0;
}