Дистанционный практикум по программированию

Даны целые числа a (от 1 до 9) и b (от 1 до 1 млрд).

Требуется найти последние 6 цифр числа a в степени b (если в результате меньше 6 цифр, вывести его целиком).

Исходные данные

Два числа a и b, разделенные пробелом.

Результат

Последние 6 цифр числа a^b.

Пример

Подсказка 1

a^b = sqr(a^b/2) при b - четном.

a^b = sqr(a^b/2)*a при b - нечетном.

Подсказка 2

Последние 6 цифр числа - это остаток от деления на 1000000. Операцию взятия остатка можно применять после каждого умножения - результат от этого не изменится.