Ваше завдання — обчислити \(n\) біноміальних коефіцієнтів за модулем \(10^9+7 \).

Біноміальний коефіцієнт \({a \choose b}\) можна обчислити за формулою \(\frac{a!}{b!(a-b)!}\). Ми припускаємо, що \(a\) і \(b\) цілі числа і \(0≤b≤a\).

Вхідні дані

Перший рядок містить ціле число \(n\) : кількість обчислень.

Після цього йде \(n\) рядків, у кожному з яких по два цілих числа \(a\) і \(b\).

Вихідні дані

Вивести кожен біноміальний коефіцієнт за модулем \(10^9+7\) .

Обмеження

• \(1≤n≤10^5\)
• \(0≤b≤a≤10^6\)

Приклад вхідних даних

3
5 3
8 1
9 5

Приклад вихідних даних

10
8
126