Trong khi xem những bức ảnh, Hồng bắt gặp một bức ảnh trong đó cô và bạn của mình đứng thành một hàng và đang thả diều. Thật không may, Hồng không còn nhớ chiếc diều nào là của bạn nào. Những sợi dây quá nhỏ để biết ai đang thả chiếc diều nào. Điều duy nhất cô nhớ là dây của các chiếc diều không bắt chéo nhau (nếu không sẽ bị rối và rơi xuống đất). Bây giờ Hồng tự hỏi có bao nhiêu cách khác nhau để mỗi người cầm một chiếc diều mà dây của chúng không đan vào nhau.

Mỗi người được coi là một điểm có tọa độ \((C_i, 0)\) và những chiếc diều như một điểm \((x_i, y_i)\). Dây diều của mỗi người là đoạn nối tọa độ của người đó với tọa độ của chiếc diều.

Yêu cầu: Đếm số lượng cấu hình các chiếc diều (cách nối mỗi người với một chiếc diều) để không có hai đoạn nào trong số các đoạn được tạo thành giao nhau hoặc chạm vào nhau.

Input

• Dòng đầu chứa số nguyên \(n\) là số lượng người và số lượng diều.
• Dòng thứ hai chứa số nguyên \(C_i\);
• Tiếp theo là \(n\) dòng, mỗi dòng chứa hai số nguyên \(x_i\) và \(y_i\) là tọa độ của mỗi chiếc diều. Các tọa độ nguyên không âm và không vượt quá \(10^4\)

Output

• Gồm một dòng duy nhất chứa một số nguyên là số cấu hình các chiếc diều thỏa mãn điều kiện, lấy dư cho \(10^9 + 7\).

Example

2
2 5
2 1
1 2

2

Constraints

• Các tọa độ nguyên không âm và không vượt quá \(10^4\).
• \(1 \le n \le 50\).

Scoring

• Subtask 1: \(n \le 20\).
• Subtask 2: Không có ràng buộc gì thêm.