#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;
    }
 
    int Sol = 0;
    for(int i = 1; i <= La ; ++i){
        for(int j = 1; j <= Lb ; ++j){
            if(a[i] != b[j]) continue ;
            if(d[i][j] == 1) C[i][j] = 1;
            else
            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;
}