Số lượng đường đi

Cho một ma trận kích thước ~n \times n~, ô giao dòng ~i~ và cột ~j~ được gọi là ô ~(i, j)~. Một robot đang ở ô ~(u, v)~ muốn di chuyển về ô góc dưới phải ~(n, n)~ của ma trận.

Yêu cầu

Hãy trả lời ~q~ truy vấn, mỗi truy vấn cho biết số cách di chuyển của robot về ô ~(n, n)~, biết rằng robot chỉ đi được xuống dưới hoặc sang phải. Vì số cách đi là rất lớn nên kết quả được lấy dư cho ~10^9 + 7~.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên ~n~ ~(2 \le n \le 10^3)~ và ~q~ ~(1 \le q \le 10^3)~, trong đó ~q~ là số truy vấn.
• ~q~ dòng tiếp theo, dòng thứ ~i~ ~(1 \le i \le q)~ chứa hai số ~u, v~ ~(1 \le u, v \le n)~ là vị trí của robot (dòng ~u~, cột ~v~) ở truy vấn ~i~.

Kết quả

Ghi trên ~q~ dòng, dòng thứ ~i~ ~(1 \le i \le q)~ là kết quả của truy vấn ~i~.

Ví dụ

Dữ liệu vào

5 3
4 4
4 2
5 5

Kết quả

2
4
1

Ràng buộc

• Có ~10\%~ số điểm có ~n = 2~.
• Có ~20\%~ số điểm có ~n = 3~.
• Có ~20\%~ số điểm có ~q = 1~.
• Có ~20\%~ số điểm có ~2 \le n, q \le 10^2~.
• Có ~30\%~ số điểm còn lại không có ràng buộc gì thêm.