#include <cstdio>
#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;

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

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] = maxim(best[i-1][j], best[i][j-1]);
        }

    for(i=0;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(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] < 0)
                        dp[i][j] += MOD;
                }
            }
        }

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

    return 0;
}