#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[1][1] = (s1[1] == s2[1] ? 1 : 0);
    for (i = 2; i <= n1; i++)
        lcs[i][1] = (lcs[i-1][1] || (s1[i] == s2[1] ? 1 : 0));
    for (j = 1; j <= n2; j++)
        lcs[1][j] = (lcs[1][j-1] || (s1[1] == s2[j] ? 1 : 0));
    
    for (i = 2; i <= n1; i++)
    for (j = 2; 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()
{
    for (i = 0; i <= n1; i++)
        nr[i][0] = 1; 
    for (j = 0; 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;
            nr[i][j] = (nr[i][j] >= 0 ? nr[i][j] : nr[i][j] + 666013);
        }
        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])
{
    for (i = 1; i <= n1; i++)
    {
        for (j = 1; 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();
    calc_nr();
    /*print(lcs);
    print(nr);
    getchar();*/
    
    fprintf(out, "%d\n", nr[n1-1][n2-1]);
    fclose(in);
    fclose(out);
    return 0;   
}