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

const int NMAX = 510, ALPHA = 30, MOD = 666013;

int N, M, Ans, Dp[NMAX][NMAX], Nr[NMAX][NMAX], PrevA[NMAX][ALPHA], PrevB[NMAX][ALPHA];
char A[NMAX], B[NMAX];

int main()
{
    freopen("subsir.in", "r", stdin);
    freopen("subsir.out", "w", stdout);
    
    gets(A + 1); N = strlen(A + 1);
    gets(B + 1); M = strlen(B + 1);
    
    for(int i = 1; i <= N; ++ i)
        for(int j = 0; j < 26; ++ j)
            if(A[i] == j + 'a')
                PrevA[i][j] = i;
            else
                PrevA[i][j] = PrevA[i - 1][j];
    
    for(int i = 1; i <= M; ++ i)
        for(int j = 0; j < 26; ++ j)
            if(B[i] == j + 'a')
                PrevB[i][j] = i;
            else    
                PrevB[i][j] = PrevB[i - 1][j];
    
    for(int i = 1; i <= N; ++ i)
        for(int j = 1; j <= M; ++ j)
            if(A[i] == B[j])
            {       
                Dp[i][j] = Dp[i - 1][j - 1] + 1;
                if(Dp[i][j] == 1) Nr[i][j] = 1;
            }else Dp[i][j] = max(Dp[i - 1][j], Dp[i][j - 1]);
    
    for(int i = 1; i <= N; ++ i)
        for(int j = 1; j <= M; ++ j)
            if(A[i] == B[j])
            {
                for(int k = 0; k < 26; ++ k)
                {
                    int PA = PrevA[i - 1][k], PB = PrevB[j - 1][k];
                    if(Dp[PA][PB] + 1 == Dp[i][j])
                        Nr[i][j] = (Nr[i][j] + Nr[PA][PB]) % MOD;
                }
                if(Dp[N][M] == Dp[i][j] && i == PrevA[N][A[i] - 'a'] && j == PrevB[M][B[j] - 'a'])
                    Ans = (Ans + Nr[i][j]) % MOD;
            }
    
    printf("%i\n", Ans);
    
    return 0;
}