#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 ( int 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[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;
    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= m; ++j )
            if ( api[n][s1[i]-'a'] == i && apj[m][s2[i]-'a'] == j )
                rez += nr[i][j];

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


	return 0;
}