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

#define Nmax 505
#define MOD 666013

using namespace std;
char A[Nmax],B[Nmax];
int DP[Nmax][Nmax],N,M;
int cnt[Nmax][Nmax];

void read()
{
    scanf("%s%s",A+1,B+1);
    A[0] = '#';
    B[0] = '#';
    N = strlen(A + 1);
    M = strlen(B + 1);
}

void precalc()
{

}

void solve()
{
    for(int i = 0; i <= N; ++i)
        cnt[i][0] = 1; /// avem un match
    for(int j = 0; j <= M; ++j)
        cnt[0][j] = 1; /// avem un match nou
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
        {
            if(A[i] == B[j])
            {
                DP[i][j] = DP[i-1][j-1] + 1;
                cnt[i][j] = cnt[i-1][j-1];
                continue;
            }
            if(DP[i-1][j] > DP[i][j-1])
            {
                DP[i][j] = DP[i-1][j];
                cnt[i][j] = cnt[i-1][j];
                continue;
            }
            if(DP[i][j-1] > DP[i-1][j])
            {
                DP[i][j] = DP[i][j-1];
                cnt[i][j] = cnt[i][j-1];
                continue;
            }
            if(DP[i][j-1] == DP[i-1][j])
            {
                DP[i][j] = DP[i-1][j];
                cnt[i][j] = (cnt[i-1][j] + cnt[i][j-1]) % MOD;
                if(DP[i-1][j-1] == DP[i][j-1])
                    cnt[i][j] = (cnt[i][j] - cnt[i-1][j-1] + MOD ) %MOD;
                continue;
            }
        }
    printf("%d\n",cnt[N][M]);
 }

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

    read();
    precalc();
    solve();

    return 0;
}