Nhà của Dế Mèn và trường làng cách nhau một con sông. Giữa dòng sông có ~N~ hòn đá nhô lên khỏi mặt nước được đánh số thứ tự từ ~1~ đến ~N~ theo hướng từ nhà đến trường. Mỗi lần đi học, Dế Mèn phải nhảy lên các hòn đá bắt đầu từ hòn đá thứ ~1~ và kết thúc ở hòn đá thứ ~N~ để lên bờ bên kia. Với mỗi bước nhảy, nếu đang đứng ở hòn đá thứ ~x~, Dế Mèn có thể nhảy đến hòn đá thứ ~x+d~, với ~d~ là một số nguyên dương thuộc một trong ~K~ đoạn các số nguyên dương rời nhau lần lượt là ~[L_1,R_1], [L_2,R_2], \ldots, [L_K,R_K]~.

Để đảm bảo an toàn, mỗi lần sang sông Dế Mèn sẽ đi theo một cách khác nhau. Hai cách khác nhau nếu như có ít nhất một bước nhảy khác nhau.

Yêu cầu: Hãy đếm số cách đi khác nhau mà Dế Mèn có thể thực hiện được.

Input

Dữ liệu đọc từ file văn bản QUASONG.INP có cấu trúc như sau:

• Dòng đầu tiên ghi hai số nguyên dương ~N, K~.
• Trong ~K~ dòng tiếp theo, dòng thứ ~i~ (~1 \le i \le K~) ghi hai số ~L_i,R_i~ (~1 \le L_i \le R_i \le N~).
• Các số trong tệp viết cách nhau ít nhất một dấu cách.

Output

• Ghi ra một số duy nhất là số cách khác nhau mà Dế Mèn có thể thực hiện được khi chia lấy dư cho ~1000000007~.

Sample Input 1

6 1
2 3

Sample Output 1

2

Sample Input 2

5 2
1 1
3 5

Sample Output 2

4

Subtask

• Có ~20\%~ số điểm tương ứng với ~N \le 10~ và ~K = 1~.
• Có ~30\%~ số điểm tương ứng với ~10 < N \le 100~ và ~K = 1~.
• Có ~20\%~ số điểm tương ứng với ~100 < N \le 10^4~ và ~1 < K \le 10~.
• Có ~30\%~ số điểm tương ứng với ~10^4 < N \le 2 \times 10^5~ và ~1 < K \le 10~.