#include <cstdio>
#include <cstring>
#include <algorithm>

#define DIM 512
#define MOD 666013
using namespace std;

int N, M;
int D[DIM][DIM], Last1[(1<<7)][DIM];
int E[DIM][DIM], Last2[(1<<7)][DIM];
char String1[DIM], String2[DIM];

int main ()
{
    freopen ("subsir.in" ,"r", stdin );
    freopen ("subsir.out","w", stdout);

    scanf ("%s", String1 + 1); N = strlen (String1 + 1);
    scanf ("%s", String2 + 1); M = strlen (String2 + 1);

    for (int k = 'a'; k <= 'z'; k ++)
    {
        for (int i = 1; i <= N; i ++)
            if (String1[i] == k)
                Last1[k][i] = i;
            else
                Last1[k][i] = Last1[k][i-1];

        for (int i = 1; i <= M; i ++)
            if (String2[i] == k)
                Last2[k][i] = i;
            else
                Last2[k][i] = Last2[k][i-1];
    }

    for (int i = 1; i <= N; i ++)
    {
        for (int j = 1; j <= M; j ++)
        {
            if (String1[i] == String2[j])
            {
                if (D[i-1][j-1] == 0)
                {
                    D[i][j] = 1;
                    E[i][j] = 1;
                }
                else
                {
                    D[i][j] = D[i-1][j-1] + 1;

                    for (int k = 'a'; k <= 'z'; k ++)
                    {
                        int poz1 = Last1[k][i-1];
                        int poz2 = Last2[k][j-1];

                        if (poz1 && poz2 && D[poz1][poz2] + 1 == D[i][j])
                            E[i][j] = (E[i][j] + E[poz1][poz2]) % MOD;
                   }
                }
            } else
                D[i][j] = max (D[i-1][j], D[i][j-1]);
        }
    }

    int answer = 0;

    if (String1[N] == String2[M])
        printf ("%d\n", E[N][M]);
    else
    {
        for (int k = 'a'; k <= 'z'; k ++)
        {
            int poz1 = Last1[k][N];
            int poz2 = Last2[k][M];

            if (poz1 && poz2 && D[N][M] == D[poz1][poz2])
                answer = (answer + E[poz1][poz2]) % MOD;
        }
        printf ("%d\n", answer);
    }

    fclose (stdin );
    fclose (stdout);

    return 0;
}