#include<cstdio>
    #include<cstring>
    using namespace std;
    #define MAX 505
    #define MOD 666013
    int N , M , c[MAX][MAX] , d[MAX][MAX];
    char A[MAX] , B[MAX] ;

    int main()
    {
        freopen("subsir.in" , "r" , stdin );
        freopen("subsir.out" , "w" , stdout );
        scanf("%s%s" , A+1 , B+1 );
        N = strlen(A+1);
        M = strlen(B+1);

        for(int i = 1 ; i <= N ; ++i )
            for(int j = 1 ; j <= M ; ++j )
            if(A[i] == B[j])
        {
            c[i][j] = c[i-1][j-1] + 1;
            if(c[i][j] == 1)d[i][j] = 1;
            else
            d[i][j] = d[i-1][j-1];
        }
            else
            {
                if(c[i-1][j] > c[i][j-1])
                {
                    c[i][j] = c[i-1][j];
                    d[i][j] = d[i-1][j];
                }
                if(c[i-1][j] < c[i][j-1])
                {
                    c[i][j] = c[i][j-1];
                    d[i][j] = d[i][j-1];
                }
                if(c[i-1][j] == c[i][j-1])
                {
                    c[i][j] = c[i-1][j];
                    d[i][j] = d[i-1][j] + d[i][j-1];
                    if(c[i-1][j-1] == c[i-1][j])
                        d[i][j] = (d[i][j] - d[i-1][j-1] + MOD )%MOD;
                }
            }
        printf("%d" , d[N][M]);
        return 0;
    }