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

#include<algorithm>

using namespace std;

const int kmod = 666013;
char first_string[550], second_string[550];
int len_first, len_second, sol, d[550][550], val[550][550];

void read(){
    assert(freopen("subsir.in","r",stdin)!=NULL);
    gets(first_string);
    gets(second_string);
    len_first = strlen(first_string);
    len_second = strlen(second_string);
}

void matched_getd(int poz1, int poz2){
    d[poz1][poz2] = d[poz1 - 1][poz2 - 1] + 1;
    if(d[poz1 - 1][poz2 - 1] + 1 == d[poz1][poz2])
        val[poz1][poz2] = (val[poz1][poz2] + val[poz1 - 1][poz2 - 1]) % kmod;
    if(d[poz1 - 1][poz2] == d[poz1][poz2])
        val[poz1][poz2] = (val[poz1][poz2] + val[poz1 - 1][poz2]) % kmod;
    if(d[poz1][poz2 - 1] == d[poz1][poz2])
        val[poz1][poz2] = (val[poz1][poz2] + val[poz1][poz2 - 1]) % kmod;
}

void unmatched_getd(int x, int y){
    d[x][y] = max(d[x - 1][y], d[x][y - 1]);
    if(d[x][y] == 0)
        val[x][y] = 1;
    else {
        if(d[x][y] == d[x - 1][y])
            val[x][y] = (val[x][y] + val[x - 1][y]) % kmod;
        if(d[x][y] == d[x][y - 1])
            val[x][y] = (val[x][y] + val[x][y - 1]) % kmod;
    }
}

void solve(){
    int i, j;
    for(i = 1; i <= len_first; ++i)
        val[i][0] = 1;
    for(i = 0; i <= len_second; ++i)
        val[0][i] = 1;
    for(i = 1; i <= len_first; ++i)
        for(j = 1; j <= len_second; ++j)
            if(first_string[i] == second_string[j])
                matched_getd(i, j);
            else
                unmatched_getd(i, j);
    sol = val[len_first][len_second];
}

void write(){
    assert(freopen("subsir.out","w",stdout)!=NULL);
    printf("%d",sol);
}

int main(){
    read();
    solve();
    write();
    return 0;
}