Remote Training on Programming

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

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

Input

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

Output

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

Sample

Hint 1

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

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

Hint 2

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