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

#define nmax 505
#define MAX(X, Y) ((X) > (Y) ? (X) : (Y))
#define star(i, j) (s1[i] == s2[j] ? 1 : 0)

char s1[nmax], s2[nmax];
int n1, n2, i, j, lcs[nmax][nmax], nr[nmax][nmax];

void calc_lcs()
{
    lcs[0][0] = (s1[0] == s2[0] ? 1 : 0);
    for (i = 1; i < n1; i++)
        lcs[i][0] = (lcs[i-1][0] || (s1[i] == s2[0] ? 1 : 0));
    for (j = 1; j < n2; j++)
        lcs[0][j] = (lcs[0][j-1] || (s1[0] == s2[j] ? 1 : 0));
    
    for (i = 1; i < n1; i++)
    for (j = 1; j < n2; j++)
        lcs[i][j] = (s1[i] == s2[j] ? lcs[i-1][j-1] + 1 : MAX(lcs[i][j-1], lcs[i-1][j]));
}

void calc_nr()
{
    //int k, l, count, rang;
    nr[0][0] = (s1[0] == s2[0] ? 1 : 0);
    for (i = 1; i < n1; i++)
        nr[i][0] = star(i, 0) ? nr[i-1][0] + 1 : nr[i-1][0];    
    for (j = 1; j < n2; j++)
        nr[0][j] = star(0, j) ? nr[0][j-1] + 1 : nr[0][j-1];    
    
    /*for (i = 1; i < n1; i++)
    for (j = 1; j < n2; j++)
        if (star(i, j))
        {
            count = 0;
            rang = lcs[i][j];
            for (k = 0; k < i; k++)
            for (l = 0; l < j; l++)            
        }*/
    
    for (i = 1; i < n1; i++)
    for (j = 1; j < n2; j++)
    {
        if (star(i, j))
            nr[i][j] = nr[i-1][j-1];
        else if (star(i-1, j-1))
            nr[i][j] = (nr[i-1][j] + nr[i][j-1] - nr[i-1][j-1])%666013;
        else if (star(i, j-1) && star(i, j-1))
        {
            if (lcs[i][j-1] == lcs[i-1][j])
                nr[i][j] = (nr[i-1][j] + nr[i][j-1])%666013;
            else
                nr[i][j] = (lcs[i][j-1] > lcs[i-1][j] ? nr[i][j-1] : nr[i-1][j]);    
        }
        else if (star(i, j-1))
            nr[i][j] = nr[i][j-1];
        else if (star(i-1, j))
            nr[i][j] = nr[i-1][j];
        else
            nr[i][j] = MAX(nr[i][j-1], nr[i-1][j]);
    }
}

void print(int a[nmax][nmax], int n1, int n2)
{
    for (i = 0; i < n1; i++)
    {
        for (j = 0; j < n2; j++)
            printf(star(i,j) ? "%d " : "0 ", a[i][j]);
        printf("\n");
    }
    printf("\n");
}


int main()
{
    FILE *in, *out;
    in  = fopen("subsir.in", "r");
    out = fopen("subsir.out", "w");
    
    fgets(s1, nmax - 1, in);
    fgets(s2, nmax - 1, in);
    n1 = strlen(s1);
    n2 = strlen(s2);
    /* delete '\n' ending the strings if the case */
    if (s1[n1 - 1] < 'a' || s1[n1 - 1] > 'z')
        s1[(n1--) - 1] = 0;
    if (s2[n2 - 1] < 'a' || s2[n2 - 1] > 'z')
        s2[(n2--) - 1] = 0;
    
    calc_lcs();
    //print(lcs, n1, n2);
    calc_nr();
    //print(nr, n1, n2);
    //getchar();
    
    fprintf(out, "%d\n", nr[n1-1][n2-1]);
    fclose(in);
    fclose(out);
    return 0;   
}