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

Дано N та K, обчислити () mod 1000000007.

Вхідні дані

Перший рядок вхідних даних містить ціле число T, яке вказує на кількість тестових випадків. Кожен тестовий випадок складається з одного рядка, що містить два цілі числа: N (1 ≤ N ≤ 1000000000) та K (1 ≤ K ≤ 4).

Вихідні дані

Для кожного тестового випадку вивести результат обчислення () mod 1000000007.

Приклади