#include <fstream>
#include <cstring>
using namespace std;
int const NM = 507 , value = 666013;
char const in [] = "subsir.in";
char const out [] = "subsir.out";
ifstream f (in);
ofstream g (out);
char v [NM] , v2 [NM];
int dp [NM][NM] , dp2 [NM][NM];
int main()
{
    int i , j , n1 , n2 , valm = 0;
    f >> v + 1 >> v2 + 1;
    n1 = strlen(v + 1);
    n2 = strlen(v2 + 1);
    for(i = 0 ; i <= n1 ; ++ i)
        dp2 [i][0] = 1;
    for(i = 0 ; i <= n2 ; ++ i)
        dp2 [0][i] = 1;
    for(i = 1 ; i <= n1 ; ++ i)
        for(j = 1 ; j <= n2 ; ++ j)
            if(v [i] == v2 [j])
                dp [i][j] = 1 + dp [i - 1][j - 1] , dp2 [i][j] = dp2 [i - 1][j - 1];
            else
            {
                if(dp [i - 1][j] > dp [i][j - 1])
                    dp [i][j] = dp [i - 1][j] , dp2 [i][j] = dp2 [i - 1][j];
                else
                    if(dp [i][j - 1] > dp [i - 1][j])
                        dp [i][j] = dp [i][j - 1] , dp2 [i][j]= dp2 [i][j - 1];
                    else
                    {
                        dp [i][j] = dp [i - 1][j] , dp2 [i][j] = (dp2 [i - 1][j] + dp2 [i][j - 1]) % value;
                        if(dp [i - 1][j - 1] == dp [i - 1][j] || v [i - 1] == v2 [j - 1])
                            dp2 [i][j] -= dp2 [i - 1][j - 1];
                    }
            }
    g << dp2 [n1][n2];
    return 0;
}