На бесконечно большом полу вам нужно уложить бесконечное количество плиток.

Каждая плитка имеет узор в виде квадратной сетки размера $n \times n$. В каждой ячейке сетки плитки вдоль её нижней и левой границ закреплена светодиодная (LED) лента; ленты имеют разные цвета, создавая красочный узор.

Узор на каждой плитке абсолютно одинаков. При укладке мы размещаем бесконечное количество плиток вплотную друг к другу без зазоров, образуя бесконечно большой узор из светодиодных лент.

Доступно $k$ различных цветов, и вам нужно выбрать соответствующие цвета в общей сложности для $2n^2$ светодиодных лент на одной плитке, после чего остальные плитки автоматически повторят эту схему раскраски. При укладке все плитки кладутся в одном и том же направлении, то есть их можно рассматривать как результат параллельного переноса одной плитки и последующего соединения без поворотов.

Прогуливаясь по полу, вы хотите узнать, сколько существует существенно различных схем раскраски плиток. Поскольку пол бесконечен, а человек при наблюдении за плитками может смотреть в разных направлениях (на север, юг, восток или запад), две схемы называются существенно одинаковыми тогда и только тогда, когда:

При наблюдении бесконечной плоскости пола, созданной двумя схемами, существует последовательность параллельных переносов или поворотов (без отражений), которая делает цвета светодиодных лент во всех позициях на полу полностью идентичными.

Входные данные

Один тест содержит несколько наборов входных данных. Первая строка входных данных содержит одно положительное целое число $T$ ($1 \le T \le 10$) — количество наборов входных данных.

Для каждого набора входных данных:

• Первая строка содержит два целых числа $n$ и $k$ ($1 \le n \le 10^9$, $1 \le k \le 10^9$), обозначающих размер узора и количество цветов соответственно.

Выходные данные

Для каждого набора входных данных выведите одну строку, содержащую одно целое число — количество существенно различных схем по модулю $10^9 + 7$.

Пример

Входные данные 1

3
1 2
2 2
114514 5201314

Выходные данные 1

3
31
377726028

Примечание

На следующем изображении показаны 19 схем построения для $n = k = 2$ (чтобы лучше проиллюстрировать эффект замощения, на каждом изображении показано 9 плиток, расположенных в виде сетки $3 \times 3$, со светодиодами тёмного и светлого цветов). Поменяв местами тёмный и светлый цвета в первых 12 схемах, можно получить ещё 12 схем, что в сумме даёт 31 схему.