#include<stdio.h>
#include<string.h>

const int LMAX = 505, MOD = 666013;

int len[LMAX][LMAX], cnt[LMAX][LMAX];
char a[LMAX], b[LMAX];

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

    scanf("%s%s", a + 1, b + 1);
    lenA = strlen(a + 1);
    lenB = strlen(b + 1);

    for(i = 1; i <= lenA; ++ i)
        cnt[i][0] = 1;
    for(j = 1; j <= lenB; ++ j)
        cnt[0][j] = 1;
    cnt[0][0] = 1;

    for(i = 1; i <= lenA; ++ i)
        for(j = 1; j <= lenB; ++ j) {
            if(a[i] == b[j]) {
                len[i][j] = len[i - 1][j - 1] + 1;
                cnt[i][j] = cnt[i - 1][j - 1];

                continue;
            }

            if(len[i - 1][j] > len[i][j - 1]) {
                len[i][j] = len[i - 1][j];
                cnt[i][j] = cnt[i - 1][j];
                
                continue;
            }

            if(len[i - 1][j] < len[i][j - 1]) {
                len[i][j] = len[i][j - 1]; 
                cnt[i][j] = cnt[i][j - 1];

                continue;
            }

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

    printf("%d\n", cnt[lenA][lenB]);
    return 0;
}