Thuận rất thích chơi game, tuy nhiên hôm nay Thuận phải học toán. Vì thế, cậu ấy đã nghiên cứu một trò chơi toán học rất thú vị như sau. Xét băng giấy dài, thẳng gồm \(n\) ô vuông liên tiếp. Bắt đầu từ ô số \(1\), cậu sẽ lần lượt "nhảy" tới ô số \(n\) theo các quy tắc đã định sẵn.
Cậu đặt ra \(k\) quy tắc, mỗi quy tắc gồm một đoạn số \([l, r]\), tức là với mỗi số \(d\) mà \(l \le d \le r\), thì Thuận sẽ được phép nhảy từ ô số \(i\) sang ô số \(i+d\) (tất nhiên \(i+d \le n\)).
Là một cậu bé thông minh và có lòng hiếu kì khám phá những kiến thức mới lạ, Thuận đã thử liệt kê tất cả các cách khác nhau để "nhảy" từ ô \(1\) tới ô \(n\) theo những quy tắc trên, nhưng cậu không biết mình đã đếm đủ chưa. Do đó, Thuận cần các bạn lập trình để tính xem có bao nhiêu cách để nhảy từ ô số \(1\) tới ô số \(n\).
Để thuận tiện, Thuận đã xác định cách thức sau để phân biệt hai cách nhảy khác nhau bất kì từ ô \(1\) tới ô \(n\): Mỗi khi đứng tại một ô nào mới, Thuận sẽ viết thêm số hiệu của ô đó vào cuối dãy số. Dãy số thu được sau mỗi lần đi tới \(n\) sẽ đặc trưng cho một cách nhảy riêng biệt.
Ví dụ, với \(n = 4\), \(k = 1\) và \(l_1 = 1, r_1 = 2\), có thể tồn tại những cách nhảy sau:

• \(1 \rightarrow 2 \rightarrow 3 \rightarrow 4\)
• \(1 \rightarrow 3 \rightarrow 4\)
• \(1 \rightarrow 2 \rightarrow 4\)

Lưu ý, vì kết quả có thể rất lớn nên hãy in ra phần dư của nó sau khi chia cho \(10^9 + 7\)

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(k\) \((1 \leq n \le 5 \times 10^{5}, 1 \le k \le 50)\).
• \(k\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_i, r_i (1 \le l_i \le r_i \le n)\) biểu thị cho một quy tắc

Output

• Gồm một dòng duy nhất chứa số cách đếm được, khi chia lấy dư cho \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(16\%\) số điểm): \(n \le 5000, k = 1\).
• Subtask \(2\) (\(16\%\) số điểm): \(n \le 5000, k = 2\).
• Subtask \(3\) (\(18\%\) số điểm): \(n \le 5000\).
• Subtask \(4\) (\(16\%\) số điểm): \(k = 1\)
• Subtask \(5\) (\(16\%\) số điểm): với \(i \neq j\) bất kì, luôn có \(\min(r_i, r_j) < \max(l_i, l_j)\)
• Subtask \(6\) (\(18\%\) số điểm): không có ràng buộc gì thêm.

Example

7 1
2 4

4