給定\(x, y, z\)  計算\((x^{y^z}) \%(10^9+7)\)

輸入格式

第一行有一個數 \(n\), \(n ≤ 10^5\) 接下來有 \(n\) 行 每行有三個數 \(x_i\) \(y_i\) \(z_i\), \(x_i, y_i, z_i ≤ 10^9\)  

輸出格式

 輸出\((x^{y^z}) \%(10^9+7)\) 以換行隔開

範例輸入

3
2 3 2
5 2006 1
5 2006 88

範例輸出

512
719269352
246590939

提示

10% 測資 \(y≤1\) 20% 測資 \(z≤1\) 其他無限制