Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
Problem hidden on 2020-10-30 17:45:28 by

ETDAQ000 - POW

Cho số nguyên dương N và K. Hãy tính NK modulo 109+7.

 

Input

Dòng đầu tiên là số lượng bộ test T (T ≤ 2000). Mỗi test gồm 1 số nguyên N và K (1 ≤ N ≤ 1010, 1 ≤ K ≤ 109).

Output

Với mỗi test, in ra đáp án trên một dòng.

Example

Input:

2

2 3

4 2

Output:

8

16


Được gửi lên bởi:ITPTIT Club
Ngày:2018-12-17
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C C++ 4.3.2 CPP CPP14 JAVA PAS-FPC PYTHON3

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.