#include <cstdio>
#include <cstring>
#define max 502
#define mod 666013

FILE *in = fopen("subsir.in","r"), *out = fopen("subsir.out","w");

char s1[max];
char s2[max];
int a[max][max] = {{0}};
int nr[max][max] = {{0}};

int main()
{
    char c = '0';

    int n = 0;
    int m = 0;

    while ( c != '\n' )
    {
        c = fgetc(in);
        s1[n++] = c;
    }

    c = '0';
    while ( c != '\n' )
    {
        c = fgetc(in);
        s2[m++] = c;
    }

    int api[max][28] = {{0}};
    int apj[max][28] = {{0}};

    for ( int i = 1; i <= n; ++i )
        for ( char j = 'a'; j <= 'z'; ++j )
            if ( s1[i-1] == j )
                api[i][j-'a'+1] = i;
            else
                api[i][j-'a'+1] = api[i-1][j-'a'+1];

    for ( int i = 1; i <= m; ++i )
        for ( char j = 'a'; j <= 'z'; ++j )
            if ( s2[i-1] == j )
                apj[i][j-'a'+1] = i;
            else
                apj[i][j-'a'+1] = apj[i-1][j-'a'+1];

    for ( int i = 1; i <= n; ++i )
    {
        for ( int j = 1; j <= m; ++j )
        {
            if ( s1[i-1] == s2[j-1] )
            {
                a[i][j] = a[i-1][j-1] + 1;
                if ( a[i][j] == 1 )
                    nr[i][j] = 1;
                else
                {
                    int ult1, ult2;
                    for ( char c = 'a'; c <= 'z'; ++c )
                    {
                        ult1 = api[i-1][c-'a'+1];
                        ult2 = apj[j-1][c-'a'+1];
                        if ( a[i][j] == a[ult1][ult2] + 1 )
                            nr[i][j] = (nr[i][j] + nr[ult1][ult2]) % mod;
                    }
                }

            }
            else
            {
                if ( a[i-1][j] > a[i][j-1] )
                    a[i][j] = a[i-1][j];
                else
                    a[i][j] = a[i][j-1];
            }


        }
    }

    int rez = 0;
    int lmax = a[n][m];

    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= m; ++j )
            if ( api[n][s1[i-1]-'a'+1] <= i && apj[m][s2[j-1]-'a'+1] <= j && a[i][j] == lmax )
                rez += nr[i][j];


    fprintf(out, "%d\n", rez);

	return 0;
}