Background

To simulate the scoring situation during a contest, the time limit of this problem is reduced by $50\%$.

Problem Description

Xiaowen has just started learning competitive programming. One day, she ran into this problem: given positive integers $a$ and $b$, find the value of $a^b$.

Here, $a^b$ means multiplying $a$ by itself $b$ times. For example, $2^3$ means multiplying three $2$'s together, and the result is $2 \times 2 \times 2 = 8$.

“So easy!” Xiaowen thought, and she quickly wrote a program. However, it produced an error during testing.

Xiaowen soon realized that all variables in her program were of type int. On most machines, the largest number that int can represent is $2^{31} - 1$, so once the computed result exceeds this number, her program will fail.

Since Xiaowen has just learned programming, she worries that using int might cause problems. Therefore, she wants you to output -1 as a warning when the value of $a^b$ exceeds ${10}^9$; otherwise, output the correct value of $a^b$.

However, Xiaowen still does not know how to implement this program, so she asks you for help.

Input Format

The input consists of one line with two positive integers $a, b$.

Output Format

Output one line: if $a^b$ does not exceed ${10}^9$, output $a^b$; otherwise output -1.

10 9

1000000000

23333 66666

-1

Hint

For $10\%$ of the testdata, it is guaranteed that $b = 1$.
For $30\%$ of the testdata, it is guaranteed that $b \le 2$.
For $60\%$ of the testdata, it is guaranteed that $b \le 30$, and $a^b \le {10}^{18}$.
For $100\%$ of the testdata, it is guaranteed that $1 \le a, b \le {10}^9$.

$\text{upd 2022.11.14/2025.04.02}$: One additional set of $\text{Hack}$ testdata has been added each time.

Translated by ChatGPT 5