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

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

char s1[max];
char s2[max];
int a[max][max];
int nr[max][max];

int main()
{
    fgets(s1, max, in);
    fgets(s2, max, in);

    int n = strlen(s1) - 1;
    int m = strlen(s2) - 1;

    int api[max][27] = {{0}};
    int apj[max][27] = {{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];
            }
        }
    }

//    for ( int i = 1; i <= n; ++i )
//    {
//        for ( int j = 1; j <= m; ++j )
//            printf("%d ", nr[i][j]);
//        printf("\n");
//    }

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



    fprintf(out, "%d\n", nr[n][m]);


	return 0;
}