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

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

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

    gets(a+1); n=strlen(a+1);
    gets(b+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] = std::max(best[i-1][j], best[i][j-1]);
        }

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

    for(i=2;i<=n;++i)
        for(j=2;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];

                while(dp[i][j] < 0) dp[i][j] +=MOD;
                dp[i][j] %= MOD;
            }
        }
    printf("%d", dp[n][m]);

    return 0;
}