#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;


#define nmax 510
#define mod 666013

int N, M, LA[nmax][30], LB[nmax][30], C[nmax][nmax], ans, Sol[nmax][nmax];
char A[nmax] , B[nmax];


int main()
{
    freopen("subsir.in", "r", stdin);
    freopen("subsir.out", "w", stdout);
    
    int i, j, k;
    A[0] = B[0] = ' ';
    fgets(A + 1, nmax, stdin);
    fgets(B + 1, nmax, stdin);
    N = strlen(A) - 2;
    M = strlen(B) - 2;
    
    
    for(i = 1; i <= N; i++)
          for(j = 1; j <= M; j++)
          {
                if(A[i] == B[j])
                       C[i][j] = C[i - 1][j - 1] + 1;
                else 
                     C[i][j] = max(C[i - 1][j], C[i][j - 1]);
                if(C[i][j] == 1 && A[i] == B[j])
                           Sol[i][j] = 1;
          }
    
    
    for(i = 1; i <= N; i++)
          for(j = 'a'; j <= 'z'; j++)
                if(A[i] == j)
                       LA[i][j - 'a'] = i;
                else
                    LA[i][j - 'a'] = LA[i - 1][j - 'a'];
                    

    for(i = 1; i <= M; i++)
          for(j = 'a'; j <= 'z'; j++)
                if(B[i] == j)
                       LB[i][j - 'a'] = i;
                else
                    LB[i][j - 'a'] = LB[i - 1][j - 'a'];
                    
                    
    for(i = 1; i <= N; i++)
          for(j = 1; j <= M; j++)
                if(A[i] == B[j])
                {
                       for(k = 'a'; k <= 'z'; k++)
                       {
                             int f = LA[i - 1][k - 'a'], s = LB[j - 1][k - 'a'];
                             if(C[f][s] + 1 == C[i][j])
                                        Sol[i][j] = (Sol[i][j] + Sol[f][s]) % mod;
                       }
                       if(C[i][j] == C[N][M] && LA[N][A[i] - 'a'] == i && LB[M][B[j] - 'a'] == j)
                                    ans = (ans + Sol[i][j]) % mod;
                }
                
                
    printf("%i\n", ans);
    return 0;
}