private ulong ModPow(ulong b, ulong pow, ulong mod)
{
    bool odd = false;

    // if the power is 2, just return the square
    if (pow == 2)
    {
        return (b * b) % mod;
    }
        // if it's 1, just return b
    if (pow == 1)
    {
        return b % mod;
    }
    if (pow == 0)
    {
        return 1;
    }
    else
    {
        // if it's an odd power, take off one
        if (pow % 2 != 0)
        {
            odd = true;
        }
        // take the even part and calculate the halves
        ulong half = ModPow(b, pow / 2, mod);
        // return two halves times eachother, times an extra b if the original power
        // was odd
        ulong res = (half * half) % mod;
        if (odd)
        {
            res = (res * b) % mod;
        }

        return res;
    }
}