Huấn luyện viên của đội hành tinh \(Z\) biết rằng, đội Trái Đất đã nắm rõ các chỉ số thể lực và chỉ số kĩ thuật của các vận động viên đội mình, vì vậy ông ta quyết định thay đổi số áo nhằm làm sai lệch những tính toán của đội Trái đất.
Đội hành tinh \(Z\) có \(m\) vận động viên đánh số từ \(1\) tới \(m\), ban đầu vận động viên thứ \(i\) mang số áo là \(i (1 \le i \le m)\)
. Huấn luyện viên chọn \(T\) đoạn, đoạn thứ \(s (1 \le s \le T)\) mô tả bằng cặp số \(L_s, R_s(1 \le L_s \le R_s \le m)\)
, rồi hoán vị số áo của các vận động viên (có thể cả \(m\) vận động viên) sao cho tất cả các vận động viên có số áo nằm trong một trong \(T\) đoạn phải mang số áo khác với số áo ban đầu của mình. Cụ thể, với một vận động viên mang số áo \(i\) mà tồn tại \(s (1 \le s \le T)\) để \(L_s \le i \le R_s\)
thì sau khi hoán vị vận động viên này phải mang số áo khác với số áo ban đầu của mình.

Yêu cầu: Hãy cho biết huấn luyện viên của đội hành tinh \(Z\) có bao nhiêu cách khác nhau để hoán vị số áo cho các vận động viên theo quy tắc trên, hai cách hoán vị số áo được gọi là khác nhau nếu có một vận động viên mang hai số áo khác nhau trong hai cách hoán vị.

Input

Vào từ thiết bị vào chuẩn theo khuôn dạng:

• Dòng đầu chứa số nguyên dương \(m, T\).
• Dòng thứ \(s(1 \le s \le T)\) trong \(T\) dòng tiếp theo chứa hai số nguyên dương \(L_s, R_s (1 \le L_s \le R_s \le m)\).

Output

• Ghi ra thiết bị ra chuẩn gồm một dòng chứa một số nguyên duy nhất là số dư của phép chia: số cách hoán vị số áo cho \((10^9 + 7)\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(m \le 10\) và \(T = 0\);
• Subtask \(2\) (\(20\%\) số điểm): \(m \le 10\) và \(T = 1\);
• Subtask \(3\) (\(20\%\) số điểm): \(m \le 10^3\) và \(T = 1; R_1 - L_1 \le 10\);
• Subtask \(4\) (\(20\%\) số điểm): \(m \le 10^3\) và \(T \le 10^3\);
• Subtask \(5\) (\(20\%\) số điểm): \(m \le 10^5\) và \(T \le 10^3\).

Example

3 1
1 2

3