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

#define MAXN 528
#define MOD 666013
#define max(a,b) ((a) > (b) ? (a) : (b))

int N, M, len;
int C[MAXN][MAXN], P[MAXN][MAXN];
int nextA[MAXN][26], nextB[MAXN][26];

char A[MAXN], B[MAXN];

void solve(void)
{
    int i, j, k, i1, j1;
    char c;

    for(i = 1; i <= N; i++)
     for(j = 1; j <= M; len = max(len, C[i][j]), j++)
        C[i][j] = (A[i]==B[j] ? C[i-1][j-1]+1:max(C[i-1][j], C[i][j-1]));

    for(i = 1; i <= N; i++)
     for(c = 'a'; c <= 'z'; c++)
     {
        for(k = i; A[k] != c && k <= N; k++) ;
        nextA[i][c-97] = (k == N+1 ? 0 : k);
     }

    for(i = 1; i <= M; i++)
     for(c = 'a'; c <= 'z'; c++)
     {
        for(k = i; B[k] != c && k <= M; k++) ;
        nextB[i][c-97] = (k == M+1 ? 0 : k);
     }

    for(i = N; i >= 1; i--)
     for(j = M; j >= 1; j--)
      if(A[i] == B[j])
      {
        if(C[i][j] == len) { P[i][j] = 1; continue; }
        for(c = 'a'; c <= 'z'; c++)
        {
            i1 = nextA[i+1][c-97], j1 = nextB[j+1][c-97];
            if(i1 && j1 && C[i1][j1] == C[i][j]+1)
            {
                P[i][j] += P[i1][j1];
                if(P[i][j] >= MOD)
                    P[i][j] -= MOD;
            }
        }
      }
}

void read_data(void)
{
    int i;
    scanf("%s\n%s\n", &A, &B), N = strlen(A), M = strlen(B);
    for(i = N; i >= 1; i--)
        A[i] = A[i-1];
    for(i = M; i >= 1; i--)
        B[i] = B[i-1];
}

void write_data(void)
{
    int res = 0, i, j;
    char c;
    for(c = 'a'; c <= 'z'; c++)
    {
        i = nextA[1][c-97], j = nextB[1][c-97];
        if(i && j && C[i][j] == 1)
            res += P[i][j];
        if(res >= MOD)
            res -= MOD;
    }
    printf("%d\n", res);
}

int main(void)
{
    freopen("subsir.in", "rt", stdin);
    freopen("subsir.out", "wt", stdout);

    read_data();
    solve();
    write_data();

    return 0;
}