1. Phát biểu bài toán

Hệ thống khóa từ trường gồm ~N~ lõi sắt từ xếp thành một hàng, đánh số từ 1 đến ~N~. Trạng thái của hệ thống được biểu diễn bởi một xâu nhị phân ~S = s_1 s_2 \dots s_N \in \{0, 1\}^N~. Ban đầu, ở thời điểm khởi tạo, tất cả các lõi đều ở trạng thái 0 (~s_i = 0, \forall i~).

Có ~M~ bộ điều khiển liên động. Bộ điều khiển thứ ~j~ (~1 \le j \le M~) được cấu hình bởi hai đoạn chỉ số ~[l_{j,1}, r_{j,1}]~ và ~[l_{j,2}, r_{j,2}]~ (~1 \le l_{j,k} \le r_{j,k} \le N~). Khi kích hoạt bộ điều khiển thứ ~j~, hệ thống bắt buộc phải chọn đúng một trong hai phương án:

• Phương án 1: Đảo trạng thái (~s_i \leftarrow s_i \oplus 1~) của tất cả các lõi ~i~ thuộc đoạn ~[l_{j,1}, r_{j,1}]~.
• Phương án 2: Đảo trạng thái (~s_i \leftarrow s_i \oplus 1~) của tất cả các lõi ~i~ thuộc đoạn ~[l_{j,2}, r_{j,2}]~.

Quy trình vận hành yêu cầu kích hoạt tất cả ~M~ bộ điều khiển, mỗi bộ đúng một lần (thứ tự kích hoạt không ảnh hưởng đến kết quả cuối cùng do tính giao hoán của phép toán ~\text{XOR}~).

Yêu cầu: Hãy tính số lượng cấu hình trạng thái cuối cùng ~S~ khác nhau có thể thu được sau khi kích hoạt xong ~M~ bộ điều khiển. Kết quả chia lấy dư cho ~10^9 + 7~.

2. Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~M~ (~1 \le N \le 2500~; ~1 \le M \le 2 \cdot 10^5~).
• ~M~ dòng tiếp theo, dòng thứ ~j~ chứa bốn số nguyên dương ~l_{j,1}, r_{j,1}, l_{j,2}, r_{j,2}~ (~1 \le l_{j,1} \le r_{j,1} \le N~; ~1 \le l_{j,2} \le r_{j,2} \le N~). (Lưu ý: hai đoạn của cùng một bộ điều khiển có thể giao nhau hoặc trùng nhau).

3. Kết quả

In ra một số nguyên duy nhất là số lượng cấu hình khác nhau theo modulo ~10^9 + 7~.

4. Ví dụ

Ví dụ 1:

• Input:

3 2
1 1 2 2
1 1 1 1

• Output:

2

• Giải thích:
  • Bộ điều khiển 1: chọn đảo ~[1, 1]~ hoặc đảo ~[2, 2]~.
  • Bộ điều khiển 2: chọn đảo ~[1, 1]~ hoặc đảo ~[1, 1]~ (cả 2 phương án đều đảo ~[1, 1]~).
  • Do đó, bộ 2 luôn đảo bit 1. Bộ 1 có 2 lựa chọn:
    • Nếu chọn ~[1, 1]~: bit 1 bị đảo 2 lần thành 0, bit 2 là 0, bit 3 là 0 ~\Rightarrow~ cấu hình 000.
    • Nếu chọn ~[2, 2]~: bit 1 bị đảo 1 lần thành 1, bit 2 bị đảo thành 1 ~\Rightarrow~ cấu hình 110.
  • Có đúng 2 cấu hình phân biệt. Kết quả là 2.

5. Subtasks

• Subtask 1 (25% số điểm): ~N \le 25, M \le 80~.
• Subtask 2 (35% số điểm): ~N \le 300, M \le 3000~.
• Subtask 3 (40% số điểm): Không có ràng buộc gì thêm (~N \le 2500, M \le 2 \cdot 10^5~).