#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MOD = 666013;

int n , m , i , j;

int D[510][510] , cnt[510][510];

char A[510] , B[510];

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);

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

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

    for (i = 1; i <= n; ++i)
     for (j = 1; j <= m; ++j)
     {
         D[i][j] = (A[i] == B[j]) ? D[i-1][j-1] + 1 : max(D[i-1][j] , D[i][j-1]);

         cnt[i][j] = (A[i] == B[j]) ?  cnt[i-1][j-1]
                                    : (D[i-1][j] == D[i][j-1]) ? cnt[i-1][j] + cnt[i][j-1] - (D[i][j-1] == D[i-1][j-1]) * cnt[i-1][j-1]
                                    : ( (D[i-1][j] > D[i][j-1]) ? cnt[i-1][j]
                                                                : cnt[i][j-1]);

         while (cnt[i][j] > MOD) cnt[i][j] -= MOD;
     }

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

    return 0;
}