#include <fstream>
#include <cstring>
#define NM 510
#define x first
#define y second
#define MOD 666013
 
using namespace std;
 
ifstream f("subsir.in");
ofstream g("subsir.out");
 
char A[NM], B[NM];
int L[NM][NM], DP[NM][NM];
int LastA[27][NM], LastB[27][NM];
int N, M;
int i, j, k, pa, pb;
 
int main ()
{
    f >> (A+1);
    N=strlen(A+1);
    f >> (B+1);
    M=strlen(B+1);
 
    memset(LastA, -1, sizeof(LastA));
    memset(LastB, -1, sizeof(LastB));
    DP[0][0]=1;
 
    for (i=1; i<=N; i++)
    {
        LastA[0][i]=0;
        for (k=1; k<=26; k++)
            LastA[k][i]=LastA[k][i-1];
 
        LastA[A[i]-'a'+1][i]=i;
    }
    for (i=1; i<=M; i++)
    {
        LastB[0][i]=0;
        for (k=1; k<=26; k++)
            LastB[k][i]=LastB[k][i-1];
 
        LastB[B[i]-'a'+1][i]=i;
    }
    LastA[0][0]=LastB[0][0]=0;
 
    for (i=1; i<=N; i++)
        for (j=1; j<=M; j++)
            if (A[i]==B[j])
            {
                L[i][j]=1+L[i-1][j-1];
 
                for (k=0; k<=26; k++)
                {
                    pa=LastA[k][i-1];
                    pb=LastB[k][j-1];
 
                    if (pa<0 || pb<0) continue;
 
                    if (L[pa][pb]+1==L[i][j])
                    {
                        DP[i][j]+=DP[pa][pb];
                        if (DP[i][j]>=MOD) DP[i][j]-=MOD;
                    }
                }
            }
            else
                L[i][j]=max(L[i-1][j], L[i][j-1]);
 
    int ANS=0;
 
    for (k=0; k<=26; k++)
    {
        pa=LastA[k][N];
        pb=LastB[k][M];
 
        if (pa<0 || pb<0) continue;
 
        if (L[pa][pb]==L[N][M])
        {
            ANS+=DP[pa][pb];
            if (ANS>=MOD) ANS-=MOD;
        }
    }
 
    g << ANS << '\n';
 
    f.close();
    g.close();
 
    return 0;
}