H. Bàn cờ
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Chung có 1 bàn cờ kích thước $$$n \times n$$$. Trên bàn cờ đó, Chung muốn đặt $$$k$$$ quân cờ. Con cờ thứ $$$i$$$ đặt ở ô ($$$r_i,c_i$$$). Chung có thể đặt 2 loại quân cờ: Xe hoặc Tượng.

Chung thắc mắc rằng, có bao nhiêu cách đặt quân cờ sao cho sau khi đặt, không quân cờ nào có thể bị ăn bởi quân cờ khác.

Input

Dòng đầu tiên chứa một số nguyên dương $$$t$$$ — số testcase.

Mỗi bộ test được mô tả như sau:

  • Dòng đầu tiên chứa 2 số nguyên dương $$$n,k$$$ ($$$1 \le n \le 10^{12}$$$), ($$$1 \le k \le 10^6$$$) — Kích thước của bàn cờ và số quân cờ cần đặt vào bàn cờ.
  • $$$k$$$ dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương $$$r_i,c_i$$$ ($$$1 \le r_i,c_i \le n$$$) — Vị trí của quân cờ thứ $$$i$$$.

Dữ liệu đầu vào đảm bảo vị trí $$$k$$$ quân cờ đôi một phân biệt.

Tổng $$$k$$$ trong tất cả các testcase không vượt quá $$$10^6$$$.

Output

Với mỗi testcase, hãy in ra số cách đặt quân cờ thỏa mãn yêu cầu bài toán chia lấy dư cho $$$10^9 + 7$$$.

Example
Input
2
10 3
1 3
2 4
10 10
10 5
1 1
5 3
7 5
9 2
10 10
Output
2
2
Note

Ở ví dụ 1, có 2 cách đặt quân cờ vào các ô thứ nhất, hai, ba như sau: Xe, Xe, Xe hoặc Xe, Xe, Tượng.

Ở ví dụ 2, có 2 cách là: Xe, Xe, Xe, Xe, Xe hoặc Xe, Xe, Xe, Tượng, Xe.