题目背景

翻译自 CSES-1712 题。

题目描述

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

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

输入格式

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

接下来的 $n$ 行，每行包含三个整数 $a$、$b$ 和 $c$：表示需要计算 $a^{b^c} \mod (10^9 + 7)$ 的值。

输出格式

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

样例

3
3 7 1
15 2 2
3 4 5

2187
50625
763327764

数据范围

• $1 \le n \le 10^5$
• $0 \le a,b,c \le 10^9$