Cho hai số nguyên dương a và b tính $a^b$ do số này quá lớn nên chỉ cần in ra kết quả là phần dư chia cho ${10}^9+7$

Input

Dòng đầu là số bộ test $1\le t\le 10$

Tiếp theo $t$ dòng mỗi dòng chứa 2 số nguyên dương có tối đa ${10}^5$ chữ số cho cả $a,b$

Output

Gồm $t$ dòng mỗi dòng là một kết quả của bài toán

Ví dụ

Input

3
2 10
3 4
132479857294579829187142959782795842 9812357942075290457894327594235

Output

1024
81
792654259