Задача 02A. Быстрое возведение в степень ≡

Условие

Возводить в степень можно гораздо быстрее, чем за n умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями:

aⁿ = (a²)^n / 2 при четном n,

aⁿ = a ⋅ a^n − 1 при нечетном n,

Реализуйте алгоритм быстрого возведения в степень. Если вы все сделаете правильно, то сложность вашего алгоритма будет O(nlog(n)).

Формат входных данных

Вводится действительное число a и целое неотрицательное число n.

Формат выходных данных

Выведите ответ на задачу с точностью до 6 знаков после запятой. Нельзя использовать стандартное возведение в степень.

Примеры тестов

2
7

128

1.00001
100000

2.7182682372