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

#define maxim(a, b) ((a > b) ? a : b)
#define NMax 505
#define MOD 666013
#define add(a, b) (((a += b) >= MOD) ? (a -= MOD) : (0))

char S[2][NMax];
int l[2];
int L[NMax][NMax], NR[NMax][NMax], cnt;
int p[2][26][NMax];

int main()
{
    int i, j, c;
    
    freopen("subsir.in", "r", stdin);
    freopen("subsir.out", "w", stdout);
    
    scanf("%s %s", S[0]+1, S[1]+1);
    l[0] = strlen(S[0]+1); l[1] = strlen(S[1]+1);

    for (j = 0; j < 2; ++j)
        for (c = 0; c < 26; ++c)
        {
            p[j][c][0] = 999999;
            for (i = 1; i <= l[j]; ++i)
                if (S[j][i] == c + 'a')
                   p[j][c][i] = i;
                else
                   p[j][c][i] = p[j][c][i-1];
        }
        
    for (i = 1; i <= l[0]; ++i)
        for (j = 1; j <= l[1]; ++j)
            if (S[0][i] == S[1][j])
               L[i][j] = 1 + L[i-1][j-1];
            else
               L[i][j] = maxim(L[i-1][j], L[i][j-1]);
    
    for (i = 1; i <= l[0]; ++i)
        for (j = 1; j <= l[1]; ++j)            
        {
            if (S[0][i] != S[1][j])
               continue;
            if (L[i][j] == 1)
            {
               NR[i][j] = 1;
               continue;
            }
            for (c = 0; c < 26; ++c)
            {
                int p1 = p[0][c][i-1];
                int p2 = p[1][c][j-1];
                if (p1 < i && p2 < j && L[p1][p2] + 1 == L[i][j])
                   add(NR[i][j], NR[p1][p2]);
            }
        }
    
    for (c = 0; c < 26; ++c)
    {
        int p1 = p[0][c][l[0]];
        int p2 = p[1][c][l[1]];
        if (p1 <= l[0] && p2 <= l[1] && L[p1][p2] == L[l[0]][l[1]])
           add(cnt, NR[p1][p2]);
    }
     
    printf("%d\n", cnt); 
        
    return 0;
}