Trên một sàn nhà rộng vô hạn, bạn cần lát vô số viên gạch.

Mỗi viên gạch có một họa tiết lưới ô vuông kích thước $n \times n$. Mỗi ô vuông của viên gạch có một dải đèn LED được gắn cố định dọc theo cạnh dưới và cạnh trái của nó, với các màu sắc khác nhau tạo nên một họa tiết đầy màu sắc.

Họa tiết trên mỗi viên gạch là hoàn toàn giống nhau. Khi lát gạch, chúng ta sẽ đặt vô số viên gạch khít cạnh nhau, tạo thành một họa tiết dải đèn rộng vô hạn.

Có $k$ màu sắc khác nhau có sẵn, và bạn cần chọn màu tương ứng cho tổng cộng $2n^2$ dải đèn trên một viên gạch, sau đó các viên gạch khác sẽ tự động sao chép cách tô màu này. Khi lát gạch, tất cả các viên gạch sẽ được đặt theo cùng một hướng, nghĩa là chúng có thể được xem như việc tịnh tiến trực tiếp một viên gạch rồi ghép lại với nhau mà không xoay.

Khi đi bộ trên sàn nhà, bạn muốn biết có bao nhiêu cách tô màu gạch khác nhau về bản chất. Vì sàn nhà là vô hạn và một người khi quan sát gạch có thể quay mặt về các hướng khác nhau (đông, tây, nam, bắc), nên hai cách tô màu được định nghĩa là giống nhau về bản chất khi và chỉ khi:

Khi quan sát mặt phẳng sàn vô hạn được tạo bởi hai cách tô màu, nếu tồn tại một chuỗi các phép tịnh tiến hoặc phép quay (không bao gồm phép đối xứng) có thể làm cho màu sắc của các dải đèn tại mọi vị trí trên sàn hoàn toàn trùng khớp, thì hai cách tô màu này được coi là giống nhau về bản chất.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ dữ liệu trong cùng một tệp. Dòng đầu tiên chứa một số nguyên dương $T$ ($1 \le T \le 10$), cho biết số lượng bộ dữ liệu.

Đối với mỗi bộ dữ liệu:

• Dòng đầu tiên chứa hai số nguyên $n$ và $k$ ($1 \le n \le 10^9$, $1 \le k \le 10^9$), lần lượt biểu thị kích thước của họa tiết và số lượng màu sắc.

Kết quả

Đối với mỗi bộ dữ liệu, in ra một dòng chứa một số nguyên duy nhất, biểu thị số lượng cách tô màu khác nhau về bản chất, chia lấy dư cho $10^9 + 7$.

Ví dụ

Dữ liệu vào 1

3
1 2
2 2
114514 5201314

Kết quả 1

3
31
377726028

Giải thích

Hình ảnh dưới đây cho thấy 19 cách xây dựng khi $n = k = 2$ (để minh họa rõ hơn hiệu ứng lát gạch, mỗi hình hiển thị 9 viên gạch được xếp theo dạng $3 \times 3$, với đèn LED có hai màu đậm và nhạt). Bằng cách hoán đổi màu đậm và màu nhạt của 12 cách đầu tiên, ta có thể thu được thêm 12 cách nữa, tạo thành tổng cộng 31 cách.