Alice và Bob vừa chơi bài với nhau. Trò chơi bao gồm \(2 \cdot n\) lá bài được đánh số lần lượt từ \(1\) đến \(2 \cdot n\). Alice nhận \(n\) lá bài trong số này, và Bob nhận \(n\) lá bài còn lại.

Trò chơi diễn ra theo lượt như sau: Alice là người đi trước. Ở lượt thứ \(i\), Alice sẽ chọn một lá bài trong số các lá còn lại của mình và đặt lên bàn, sau đó Bob cũng sẽ chọn một lá bài để đấu với lá của Alice. Nếu số trên lá bài của Bob cao hơn của Alice, Bob sẽ thắng lượt đó; ngược lại, Alice thắng. Sau đó, cả hai tiếp tục chơi các lượt tiếp theo, mỗi người còn \(n - i\) lá bài. Sau \(n\) lượt chơi, người nào thắng nhiều lượt hơn sẽ là người thắng chung cuộc. Nếu cả hai thắng cùng số lượt thì trò chơi kết thúc với kết quả hòa.

Alice và Bob đã có một đêm chơi bài vui vẻ cùng nhau, nhưng giờ Alice đã quên mất trò chơi đã diễn ra như thế nào. Alice chỉ nhớ một vài lá bài được chơi trong một số lượt và kết quả của một số lượt. Nói cách khác, Alice chỉ nhớ \(m\) mẩu thông tin, mẩu thông tin thứ \(i\) được biểu diễn bởi bộ bốn số \((p_i, a_i, b_i, r_i)\) có ý nghĩa như sau:

• \(p_i\) là số thứ tự của lượt chơi.
• \(a_i\) là số của lá bài Alice đã chơi ở lượt thứ \(p_i\). Nếu \(a_i = 0\), Alice không nhớ chính xác lá bài này.
• \(b_i\) là số của lá bài Bob đã chơi ở lượt thứ \(p_i\). Nếu \(b_i = 0\), Alice không nhớ chính xác lá bài này.
• \(r_i\) là kết quả của lượt chơi thứ \(i\). \(r_i = 0\) nếu Alice thắng và \(r_i = 1\) nếu Bob thắng.

Alice không quá xuất sắc trong việc ghi nhớ, vì vậy có thể có các lượt chơi không hợp lệ, chẳng hạn như một lá bài được chơi nhiều lần hoặc lá bài có số cao hơn lại thua. Trong các trường hợp này, sẽ không có cách chơi nào phù hợp với trí nhớ của Alice.

Alice muốn biết có bao nhiêu cách chơi hợp lệ khác nhau khớp với trí nhớ của Alice và kết quả là Alice thắng, Bob thắng hoặc cả 2 hòa. Hai cách chơi được coi là khác nhau nếu có một lượt mà Alice hoặc Bob đã chơi một lá bài trong cách này và một lá bài khác trong cách kia. Vì các số này có thể rất lớn, hãy in kết quả modulo \((10^9 + 7)\).

Input

• Dòng đầu tiên gồm một số nguyên \(t\) (\(1 \le t \le 10\)) là số test case.
• Mỗi test case có dạng:
  • Dòng đầu chứa hai số nguyên \(n\) và \(m\) (\(1 \le n \le 10^5, 0 \le m \le \min(300, n)\)).
  • Trong \(m\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(p_i, a_i, b_i, r_i\) (\(1 \le p_i \le n, 0 \le a_i, b_i \le 2 \cdot n, 0 \le r_i \le 1\)).
• Dữ liệu vào luôn đảm bảo tất cả giá trị \(p_i\) đều khác nhau.

Output

• Với mỗi test case, in ra ba số \(A, B, D\) lần lượt là số cách chơi khác nhau khớp với trí nhớ của Alice và kết quả là Alice thắng, Bob thắng và cả 2 hòa, modulo \(10^9 + 7\).

Example

5
3 0
4 0
3 3
1 1 0 1
2 2 0 1
3 5 0 0
3 1
2 3 0 0
5 3
3 2 7 0
2 5 0 0
1 0 0 0

360 360 0
12600 12600 15120
0 4 0
36 12 0
0 0 0

Scoring

• Subtask \(1\) (\(14\%\) số điểm): \(n \le 5\).
• Subtask \(2\) (\(15\%\) số điểm): \(m = 0\).
• Subtask \(3\) (\(16\%\) số điểm): \(m \le 8\) và \(a_i > 0\) hoặc \(b_i > 0\) với \(1 \le i \le m\).
• Subtask \(4\) (\(11\%\) số điểm): \(a_i = b_i = 0\) với \(1 \le i \le m\).
• Subtask \(5\) (\(12\%\) số điểm): \(n \le 10\).
• Subtask \(6\) (\(13\%\) số điểm): \(n = m\).
• Subtask \(7\) (\(19\%\) số điểm): Không có ràng buộc gì thêm.