int qmul(int x,int y)
{
    int s=0;
    while(y)
    {
        if(y&1) s=(s+x)%p;
        x=(x+x)%p;
        y>>1;
    }
    return s%p;
}

int qpow(int x,int y)
{
    int s=1;
    while(y)
    {
        if(y&1) s=qmul(s,x);
        x=qmul(x,x);
        y>>1;
    }
    return s%p;
}