#include <bits/stdc++.h>
#define MOD 666013
#define maxN 505
using namespace std;
char a[maxN],b[maxN];
int n,m,i,j;
int lcs[maxN][maxN];
int dp[maxN][maxN];
int main()
{
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    gets(a+1);
    gets(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])
                lcs[i][j]=1+lcs[i-1][j-1];
            else lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1]);
    for(i=1;i<=n;i++)
        dp[i][1]=1;
    for(i=1;i<=m;i++)
        dp[1][i]=1;
    for(i=2;i<=n;i++)
        for(j=2;j<=n;j++)
        {
            if(a[i]==b[j])
            {
                dp[i][j]=dp[i-1][j-1];
                continue;
            }
            if(lcs[i][j]==lcs[i-1][j])
            {
                dp[i][j]+=dp[i-1][j];
                if(dp[i][j]>=MOD)
                    dp[i][j]-=MOD;
            }
            if(lcs[i][j]==lcs[i][j-1])
            {
                dp[i][j]+=dp[i][j-1];
                if(dp[i][j]>=MOD)
                    dp[i][j]-=MOD;
            }
            if(lcs[i][j]==lcs[i-1][j-1])
            {
                dp[i][j]-=dp[i-1][j-1];
                if(dp[i][j]<0)
                    dp[i][j]+=MOD;
            }
        }
    printf("%d",dp[n][m]);
    return 0;
}