거듭 제곱 빠른 계산

 

i64 ipow(i64 n, i64 x)
{
    if (x == 0)
        return 1;

    i64 half = ipow(n, x / 2);
    half = (half * half) % MOD;

    if (x % 2 == 0)
        return half;

    return (half * n) % MOD;
}