Ваше завдання — обчислити ~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