//time complexity:- O(log p)

ll bpow(ll b, ll p, ll m)
{
    // power is 0 or base is 1 return 1
    if (p == 0 || b == 1)
        return 1;

    // if power is odd
    if (p & 1)
    {
        p >>= 1; // divide power by 2
        ll t = bpow(b, p, m);
        t = (1ll * t * t % m);
        return (1ll * b * t % m);
    }
    // if power is even
    else
    {
        p >>= 1;
        ll t = bpow(b, p, m);
        return (1ll * t * t % m);
    }
}