#include <bits/stdc++.h>
using namespace std;

char a[505], b[505];
int d[505][505];
int C[505][505];
int L1[505][27], L2[505][27];
const int MOD  = 666013;
int main()
{
    freopen("subsir.in", "r", stdin);
    freopen("subsir.out", "w", stdout);

    scanf("%s", a + 1);
    scanf("%s", b + 1);

    int La = strlen(a + 1), Lb = strlen(b + 1);
    a[++La] = 'a'; b[++Lb] = 'a';
    for(int i = 1; i <= La ; ++i)
        for(int j = 1; j <= Lb ; ++j)
            d[i][j] = max(d[i - 1][j - 1] + (a[i] == b[j]) , max(d[i - 1][j], d[i][j - 1]));

    for(int i = 1; i <= La ; ++i){
        for(int k = 0; k < 26 ; ++k)
            L1[i][k] = L1[i - 1][k];
        L1[i][a[i] - 'a'] = i;
    }
    for(int i = 1; i <= Lb ; ++i){
        for(int k = 0; k < 26 ; ++k)
            L2[i][k] = L2[i - 1][k];
        L2[i][b[i] - 'a'] = i;
    }

    for(int k = 0; k < 26 ; ++k){
        int pos1 = 0, pos2 = 0;
        for(int i = 1; i <= La ; ++i)
        if(a[i] - 'a' == k) {pos1 = i; break ;}
        for(int i = 1; i <= Lb ; ++i)
        if(b[i] - 'a' == k) {pos2 = i; break ;}
        if(pos1 == 0 || pos2 == 0) continue ;
        if(d[pos1][pos2] == 1)
        C[pos1][pos2] = 1;
    }

    int Sol = 0;
    for(int i = 1; i <= La ; ++i){
        for(int j = 1; j <= Lb ; ++j){
            if(a[i] != b[j]) continue ;
            for(int k = 0; k < 26 ; ++k){
                int l = L1[i - 1][k];
                int c = L2[j - 1][k];
                if(!(l > 0 && c > 0) || d[l][c] + 1 != d[i][j]) continue ;
                C[i][j] += C[l][c];
                if(C[i][j] >= MOD) C[i][j] -= MOD;
            }
        }
    }
    printf("%d", C[La][Lb]);
    return 0;
}