Một bàn cờ kích thước N * N. Người ta đặt một con tốt trắng lên ô (1, 1) và M con tốt đen lên các ô còn lại của bàn cờ sao cho không có 2 con tốt nào trên cùng một ô. Ta có thể di chuyển con tốt trắng đến ô bên phải hoặc bên dưới ô đang đứng nếu như ô đó không chứa tốt đen.

Yêu cầu: Tính xem có bao nhiêu cách di chuyển con tốt trắng đến ô (N, N). Do kết quả có thể rất lớn nên chỉ đưa ra phần dư của kết quả trong phép chia cho 10^9.

Input

Dòng đầu tiên ghi 2 số nguyên N, M (2 ≤ N ≤ 1000, 0 ≤ M ≤ N * N).
M dòng sau, dòng thứ i ghi 2 số nguyên x y là tọa độ ô đặt con tốt đen thứ i.

Output

Một dòng duy nhất chứa một số nguyên là kết quả của bài toán.

Ví dụ

Input
2 1
1 2

Output
1