Сума степенів Версія I

Вхідні дані

Перший рядок містить одне ціле число $T$ ( $1 \leq T \leq 1 0^{5}$ 1 \leq T \leq 10^5) — кількість тестів.

Кожен з наступних $T$ рядків містить два цілих числа $N$ і $K$ ( $1 \leq N \leq 1 0^{9}$ 1 \leq N \leq 10^9, $1 \leq K \leq 4$ 1 \leq K \leq 4).

Для кожного тесту виведіть значення виразу за модулем $1000000007$ .

Приклад 1

Loading