#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <utility>

using namespace std;

const int MOD = 666013;


char a[510],b[510];
int best[510][510];
int cate[510][510];
int last_a['z'-'a'][510];
int last_b['z'-'a'][510];

int lena,lenb;

void preproc(char * sir , int last_x['z'-'a'][510])
{
    char c,*p = sir;
    while(*p){
        for(c = 'a' ; c <= 'z' ; ++ c){
            last_x[c-'a'][p-sir+1] = last_x[c-'a'][p-sir];
            if(*p == c)
                last_x[c-'a'][p-sir+1] = p-sir+1;
        }
        ++p;
    } 
}

void prima()
{
    preproc(a+1,last_a);
    preproc(b+1,last_b);
    lenb = strlen(b+1);
    int i,j;
    int l_a,l_b;
    char c;
    for(i = 1 ; i <= lena ; ++ i)
        for(j = 1 ; j <= lenb ; ++ j){
            best[i][j] = max(best[i-1][j],best[i][j-1]);
            if(a[i] == b[j]){
                best[i][j] = max(best[i][j], best[i-1][j-1] + 1 );
                for(c = 'a' ; c <= 'z' ; ++ c){
                    l_a = last_a[c-'a'][i-1];
                    l_b = last_b[c-'a'][j-1];
                    if(best[l_a][l_b] +1 == best[i][j])
                        cate[i][j] = (cate[i][j] + cate[l_a][l_b]) % MOD;
                }
                if(cate[i][j] == 0)
                    cate[i][j] = 1;
            }
        }
}



void doua()
{
    int sol = 0;
    char c;
    int bestest = best[lena][lenb];
    int l_a,l_b;
    for(c = 'a' ; c <= 'z' ; ++ c){
        l_a = last_a[c-'a'][lena];
        l_b = last_b[c-'a'][lenb];
        if(best[l_a][l_b] == bestest)
            sol = (sol + cate[l_a][l_b]) % MOD;
    }
    printf("%d\n",sol);
}

int main()
{
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    scanf("%s\n%s\n",a+1,b+1);
    lena = strlen(a+1);
    lenb = strlen(b+1);
    prima();
    doua();
    return 0;
}