#include <cstdio>
#include <string.h>
#define MAXN 510
#define MOD 666013

char a[MAXN+2], b[MAXN+2];
int best[MAXN+1][MAXN+1], dp[MAXN+1][MAXN+1], n, m;

inline int maxim(int a, int b){
    return ((a>b) ? a : b);
}

int main()
{
    freopen("subsir.in","r", stdin);
    freopen("subsir.out", "w",stdout);

    scanf("%s%s", a+1, b+1);
    n=strlen(a+1);
    m=strlen(b+1);

    int i, j;

    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
        {
            if(a[i] == b[i])
                best[i][j] = best[i-1][j-1] + 1;
            else best[i][j] = maxim(best[i-1][j], best[i][j-1]);
        }

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

    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
        {
            if(a[i] == b[i])
                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(best[i][j-1] == best[i][j])
                    dp[i][j] += dp[i][j-1];

                if(best[i-1][j-1] == best[i][j]){
                    dp[i][j] -= dp[i-1][j-1];
                    dp[i][j] += MOD;
                }
                dp[i][j] %= MOD;
            }
        }

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

    return 0;
}