Nhiệm vụ của bạn là tính ~m~ tổ hợp ~C_n^k~ theo modulo ~10^9 + 7~.

Tổ hợp ~C_n^k~ có thể tính theo công thức. ~C_n^k = \frac{n!}{(n - k)!k!}~.

Input

• Dòng đầu tiền gồm số ~m~.

• ~m~ dòng tiếp theo. Mỗi dòng gồm 2 số ~n~, ~k~.

Output

• Gồm ~m~ dòng. Mỗi dòng là kết quả của ~C_n^k~ theo modulo ~10^9 + 7~.

Giới hạn

• ~1 \le m \le 10^5~

• ~0 \le k \le n \le 10^6~

Example

Input

3
5 3
8 1
9 5

Output

10
8
126