Remote Training on Programming

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

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

Input

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

Output

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

Sample