題目描述

給定兩個正整數 a, b，求 a^b mod 1000000007 的值。

輸入格式

第一行一個正整數 T，表示接下來有 T 個測試用例。

接下來 T 行，每行兩個正整數 a, b，以空格分隔。

輸出格式

對於每個測試用例，隔行輸出 a^b mod 1000000007 的值。

Samples

3
1 1
2 3
2 10

1
8
1024

提示

保證 T ≤ 10⁵, a ≤ 10⁹, b ≤ 10¹⁸。

原始資料

• Zero1 題號：b283
• Hydro 題號：Z1283
• Locale：zh_TW
• Display：practice