На нескінченно великій підлозі вам потрібно вкласти нескінченну кількість плиток.

Кожна плитка має візерунок у вигляді квадратної сітки розміру $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 схему.