#include <cstring>
#include <cstdio>
#define M 666013
#define N 505
using namespace std;
char s1[N],s2[N];
int dp[N][N],nr[N][N],n,m;

void Read()
{
    freopen("subsir.in","r",stdin);

    scanf("%s",s1+1);n=strlen(s1+1);
    scanf("%s",s2+1);m=strlen(s2+1);

}

void Dynamic()
{
    int i,j;

    for (i=0;i<=n;++i)
        nr[i][0]=1;

    for (j=0;j<=m;++j)
        nr[0][j]=1;

    for (i=1;i<=n;++i)
        for (j=1;j<=m;++j)
            if (s1[i]==s2[j]) {
                               dp[i][j]=dp[i-1][j-1]+1;
                               nr[i][j]=nr[i-1][j-1];
                              }
            else if (dp[i-1][j]<dp[i][j-1]) {
                                             dp[i][j]=dp[i][j-1];
                                             nr[i][j]=nr[i][j-1];
                                            }
                 else if (dp[i-1][j]>dp[i][j-1]) {
                                                  dp[i][j]=dp[i-1][j];
                                                  nr[i][j]=nr[i-1][j];
                                                 }
                      else {
                           dp[i][j]=dp[i-1][j];
                           nr[i][j]=(nr[i-1][j]+nr[i][j-1])%M;
                           if (dp[i-1][j-1]==dp[i][j]) nr[i][j]=(nr[i][j]-nr[i-1][j-1]+M)%M;
                           }
}

void Write()
{
    freopen("subsir.out","w",stdout);

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

int main()
{
    Read();
    Dynamic();
    Write();
    return 0;
}