분할 정복을 이용한 제곱 수 계산 (logP)

#define P 1000000007

long long power(long long x, long long y) {
    long long ReturnValue = 1;
    while (y > 0) {
        if (y % 2) {
            ReturnValue *= x;
            ReturnValue %= P;
        }
        x *= x;
        x %= P;
        y /= 2;
    }
    return ReturnValue;
}