Your task is to efficiently calculate values $a^b$ modulo $10^9+7$. Note that in this task we assume that $0^0=1$.

The first input line contains an integer n: the number of calculations. After this, there are $n$ lines, each containing two integers $a$ and $b$.

Print each value $a^b$ modulo $10^9+7$. $$ 1 \le n \le 2 \cdot 10^5 $$ $$ 0 \le a,b \le 10^9 $$