Di atas lantai yang berukuran tak hingga, Anda perlu memasang ubin dalam jumlah tak hingga.

Setiap ubin memiliki pola kisi persegi berukuran $n \times n$. Setiap sel kisi pada ubin memiliki strip lampu LED yang dipasang di sepanjang tepi bawah dan tepi kirinya, dengan warna-warna berbeda yang menciptakan pola penuh warna.

Pola pada setiap ubin persis sama. Saat memasang ubin, kita akan menempatkan ubin dalam jumlah tak hingga secara berdampingan tanpa celah, membentuk pola strip lampu yang berukuran tak hingga.

Tersedia $k$ warna berbeda, dan Anda perlu memilih warna yang sesuai untuk total $2n^2$ strip lampu pada satu ubin, setelah itu ubin-ubin lainnya akan secara otomatis meniru skema pewarnaan ini. Saat memasang ubin, semua ubin akan dipasang dengan arah yang sama, artinya ubin-ubin tersebut dapat dipandang sebagai hasil translasi langsung dari satu ubin lalu disambungkan bersama tanpa rotasi.

Saat Anda berjalan di atas lantai, Anda ingin mengetahui berapa banyak skema pewarnaan ubin yang berbeda secara esensial. Karena lantai berukuran tak hingga, dan seseorang mungkin menghadap ke arah yang berbeda (utara, selatan, timur, barat) saat mengamati ubin, dua skema didefinisikan sama secara esensial jika dan hanya jika:

Saat mengamati bidang lantai tak hingga yang dibuat oleh kedua skema tersebut, jika terdapat serangkaian translasi atau rotasi (tidak termasuk pencerminan) yang dapat membuat warna strip lampu di semua posisi pada lantai menjadi sama persis, maka kedua skema ini dianggap sama secara esensial.

Masukan

Terdapat beberapa kasus uji dalam satu berkas masukan. Baris pertama masukan berisi sebuah bilangan bulat positif $T$ ($1 \le T \le 10$), yang menyatakan jumlah kasus uji.

Untuk setiap kasus uji:

• Baris pertama masukan berisi dua bilangan bulat $n$ dan $k$ ($1 \le n \le 10^9$, $1 \le k \le 10^9$), yang masing-masing menyatakan ukuran pola dan jumlah warna.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi satu bilangan bulat yang menyatakan jumlah skema yang berbeda secara esensial, modulo $10^9 + 7$.

Contoh

Masukan 1

3
1 2
2 2
114514 5201314

Keluaran 1

3
31
377726028

Catatan

Gambar berikut menunjukkan 19 skema konstruksi untuk $n = k = 2$ (untuk mengilustrasikan efek pemasangan ubin dengan lebih baik, setiap gambar menampilkan 9 ubin yang disusun dalam pola $3 \times 3$, dengan LED berwarna gelap dan terang). Dengan menukar warna gelap dan terang pada 12 skema pertama, dapat diperoleh 12 skema lainnya, sehingga menghasilkan total 31 skema.