Farmer John có \(N\) con bò (\(2\leq N\leq 5\cdot 10^6\)) và đang cố nhờ vào tính lười biếng của chúng để sắp xếp một mảng số nguyên không âm \(A\) độ dài \(N\). Ông có rất nhiều thùng nặng nên xếp các con bò thành một hàng, con bò \(i+1\) đứng sau con bò \(i\), rồi giao \(a_i\) thùng cho con bò \(i\) (\(0\le a_i\)).

Bò vốn lười biếng nên luôn tìm cách đẩy việc cho người khác. Theo thứ tự từ bò \(1\) đến bò \(N-1\), mỗi con bò nhìn con bò đứng sau mình. Nếu bò \(i\) có nhiều thùng hơn hẳn bò \(i+1\), bò \(i\) cho rằng điều này “không công bằng” và đưa một thùng của mình cho bò \(i+1\). Quá trình này lặp lại cho tới khi mọi con bò đều hài lòng.

Sau đó, Farmer John ghi lại số thùng \(b_i\) mà mỗi bò \(i\) đang giữ và tạo mảng \(B\) từ các giá trị này. Nếu \(B=sorted(A)\) thì Farmer John sẽ vui. Không may, Farmer John đã quên tất cả trừ \(Q\) giá trị (\(2\leq Q\leq\min(N,100)\)) trong \(A\). May mắn thay, trong đó có số thùng ông định giao cho con bò đầu tiên và con bò cuối cùng. Mỗi giá trị FJ nhớ được có dạng \(c_i\;v_i\), biểu thị \(a_{c_i}=v_i\) (\(1\leq c_i\leq N\), \(1\le v_i\leq 10^9\)). Hãy xác định số cách khác nhau để điền các giá trị còn thiếu sao cho ông sẽ vui, lấy modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách \(N\) và \(Q\), lần lượt là số bò và số giá trị được nhớ.

\(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách \(c_i\;v_i\), biểu thị ban đầu bò \(c_i\) giữ \(v_i\) thùng. Đảm bảo \(c_1=1\), \(c_Q=N\) và \(c_i<c_{i+1}\) (thứ tự các con bò tăng nghiêm ngặt).

Dữ liệu ra

In ra số cách khác nhau modulo \(10^9+7\) để gán các giá trị \(a_i\) sao cho Farmer John sẽ vui sau khi các con bò thực hiện phép sắp xếp lười biếng. Đảm bảo có ít nhất một cách gán hợp lệ.

Ví dụ

3 2
1 3
3 2

2

6 3
1 1
3 3
6 5

89

Phân nhóm

• Dữ liệu 3–4: \(N,v_i\le 100\).
• Dữ liệu 5–6: \(N\le 100\) và \(v_i\leq 10^6\).
• Dữ liệu 7–9: \(N\leq 2\cdot 10^5\) và \(v_i\le 10^6\).
• Dữ liệu 10–12: \(N\leq 2\cdot 10^5\).
• Dữ liệu 13–15: Không có ràng buộc bổ sung.

Đề bài: Suhas Nagar.

Nguồn

USACO 2025 US Open Contest, Platinum — Lazy Sort: https://usaco.org/index.php?page=viewproblem2&cpid=1525