Ожерелья

Сколько различных ожерелий из $n$ бусин $k$ цветов существует, если ожерелья, отличающиеся поворотом, считаются одинаковыми? Ответ по модулю $10^9 + 7$.

В первой строке $q$ ($1 \le q \le 300$). В каждой из следующих $q$ строк — числа $n$ и $k$ ($1 \le n \le 10^6$, $1 \le k \le 10^9$).

Для каждого запроса выведите количество ожерелий по модулю $10^9 + 7$.