题目背景

翻译自 CSES-1095 题。

题目描述

你的任务是高效地计算 $a^b \mod (10^9 + 7)$ 的值。

注意，在本题中我们假设 $0^0 = 1$。

输入格式

第一行包含一个整数 $n$：计算的数量。

接下来的 $n$ 行，每行包含两个整数 $a$ 和 $b$：表示需要计算 $a^b$ 的值。

输出格式

对于每个查询，输出 $a^b \mod (10^9 + 7)$ 的结果。

样例

3
3 4
2 8
123 123

81
256
921450052

说明/提示

$1 \leq n \leq 2 \cdot 10^5$；

$0 \leq a,b \leq 10^9$。