#include<cstdio>
#include<cstring>
#define MAXN 510
#define MOD 666013
using namespace std;
char a[MAXN],b[MAXN];
int best[MAXN][MAXN],dp[MAXN][MAXN];
int maximum(int x,int y){
    if(x<y)
        return y;
    return x;
}
int main(){
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    int n,m,i,j;
    scanf("%s%s",a,b);
    n=strlen(a);
    m=strlen(b);
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
            if(a[i]==b[j])
                best[i][j]=best[i-1][j-1]+1;
            else
                best[i][j]=maximum(best[i][j-1],best[i-1][j]);
    for(i=0;i<n;i++)
        dp[i][0]=1;
    for(j=0;j<m;j++)
        dp[0][j]=1;
    for(i=1;i<n;i++)
        for(j=1;j<m;j++)
            if(a[i]==b[j])
                dp[i][j]=dp[i-1][j-1];
            else{
                if(best[i-1][j]==best[i][j]){
                    dp[i][j]+=dp[i-1][j];
                    if(dp[i][j]>=MOD)
                        dp[i][j]-=MOD;
                }
                if(best[i][j-1]==best[i][j]){
                    dp[i][j]+=dp[i][j-1];
                    if(dp[i][j]>=MOD)
                        dp[i][j]-=MOD;
                }
                if(best[i-1][j-1]==best[i][j]){
                    dp[i][j]+=dp[i-1][j-1];
                    if(dp[i][j]>=MOD)
                        dp[i][j]-=MOD;
                }
            }
    printf("%d",dp[n-1][m-1]);
    return 0;
}