Возведите натуральное число N в целую неотрицательную степень P.
Степень эффективно вычисляется по следующим правилам:
- Если P = 0, то NP = 1;
- Если P > 0 и P — чётное, то
; - Если P > 0 и P — нечётное, то
.
Выходные данные
Выведите одно целое число — остаток от деления NP на 1000000007.