Оленка робить штамп для візерунка на стрічці. Штамп — це смужка з клітинок, кожну з яких пофарбовано в один з кольорів. Позначимо кольори клітинок зліва направо w_1, w_2, \ldots, w_n (1 \le w_i \le k).
Щоб відбитки на стрічці не можна було сплутати, Оленці потрібен вдалий штамп. Штамп називається вдалим, якщо жоден його початок не пофарбований так само, як кінець такої самої довжини. Тобто для кожного від до n - 1 перші клітинок відрізняються від останніх :
Штамп з однієї клітинки завжди вдалий.
Наприклад, при k = 3 штампи , і вдалі, а штампи (l = 1), (l = 2) і (l = 1, 2, 3) — ні.
Задано запитів. Для кожного запиту порахуйте кількість вдалих штампів з клітинок, пофарбованих у кольорів. Оскільки відповіді можуть бути дуже великими, виведіть їх за модулем 10^9 + 7.
Перший рядок містить одне ціле число (1 \le t \le 10^5) — кількість запитів.
Кожен із наступних рядків містить два цілі числа і (1 \le n \le 10^6, 1 \le k \le 10^9) — кількість клітинок штампа і кількість кольорів.
Гарантується, що сума по всіх запитах не перевищує 10^6.
Для кожного запиту виведіть в окремому рядку кількість вдалих штампів з клітинок, пофарбованих у кольорів, за модулем 10^9 + 7.
Приклад 1
Приклад 2
У першому прикладі:
Для n = 1 усі штампів вдалі.
Для n = 2, k = 3 штамп вдалий тоді й лише тоді, коли його дві клітинки мають різні кольори: 3 \cdot 2 = 6 штампів.
Для n = 3, k = 2 вдалими є штампи , , і .
Для n = 4, k = 2 вдалими є штампи , , , , і . Наприклад, штамп не є вдалим, бо його перші дві клітинки пофарбовано так само, як дві останні, а штамп не є вдалим, бо він починається й закінчується кольором .