#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, r, count, rang;
    nr[0][0] = (s1[0] == s2[0] ? 1 : 0);
    for (i = 1; i < n1; i++)
        nr[i][0] = 1;    
    for (j = 1; j < n2; j++)
        nr[0][j] = 1;    
    
    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 (lcs[i][j-1] == lcs[i-1][j])
        {
            
            nr[i][j] = (nr[i-1][j] + nr[i][j-1])%666013;
            if (lcs[i][j-1] == lcs[i-1][j-1])
                  nr[i][j] = (nr[i][j] - nr[i-1][j-1])%666013;
            /*if (i == 6 && j == 5)
            {
                printf("\n\n", lcs[i-1][j-1], lcs[i-1][j], lcs[i][j-1]);
                printf("\nnr[%d][%d] = %d\n", i-1, j-1, nr[i-1][j-1]);
                printf("\nnr[%d][%d] = %d\n", i-1, j, nr[i-1][j]);
                printf("\nnr[%d][%d] = %d\n", i, j-1, nr[i][j-1]);
                printf("\nnr[%d][%d] = %d\n", i, j, nr[i][j]);
            }*/
        }
        else
            nr[i][j] = (MAX(lcs[i][j-1], lcs[i-1][j]) == lcs[i][j-1] ? 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("%d ", 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;   
}