Cho hai số nguyên dương \(a\),\(m\).

Tính giá trị biểu thức \(X = a^1 \times a^2 \times ... \times a^m\)

Constraints

• \(a,m \le 10^6\)

Subtask 1 [30%]

• \(a,m \le 10\)

Subtask 2 [70%]

• Không ràng buộc gì thêm.

Input

• Dòng 1: \(t\) \((t \le 100)\) - số câu hỏi.
• \(t\) dòng tiếp theo, mỗi dòng gồm hai số nguyên dương \(a\),\(m\).

Output

• \(X \mod (10^9 + 7)\)

Example input

1
2 3

Example output

64