题目背景

翻译自 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 \leq n \leq 10^5$；

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