Візерунок#13075

Візерунок

1 секунда
256 мегабайтів

Оленка робить штамп для візерунка на стрічці. Штамп — це смужка з клітинок, кожну з яких пофарбовано в один з кольорів. Позначимо кольори клітинок зліва направо w_1, w_2, \ldots, w_n (1 \le w_i \le k).

Щоб відбитки на стрічці не можна було сплутати, Оленці потрібен вдалий штамп. Штамп називається вдалим, якщо жоден його початок не пофарбований так само, як кінець такої самої довжини. Тобто для кожного від до n - 1 перші клітинок відрізняються від останніх :

w_1 w_2 \ldots w_l \ne w_{n-l+1} w_{n-l+2} \ldots w_n.

Штамп з однієї клітинки завжди вдалий.

Наприклад, при 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

Loading
Loading

Приклад 2

Loading
Loading

Примітка

У першому прикладі:

  • Для n = 1 усі штампів вдалі.

  • Для n = 2, k = 3 штамп вдалий тоді й лише тоді, коли його дві клітинки мають різні кольори: 3 \cdot 2 = 6 штампів.

  • Для n = 3, k = 2 вдалими є штампи , , і .

  • Для n = 4, k = 2 вдалими є штампи , , , , і . Наприклад, штамп не є вдалим, бо його перші дві клітинки пофарбовано так само, як дві останні, а штамп не є вдалим, бо він починається й закінчується кольором .