Cho một bàn cờ hình vuông kích thước ~m \times m~. Các hàng và cột của bàn cờ được đánh số từ ~1~ đến ~m~.

Bạn đặt các quân cờ lên bàn cờ sao cho mỗi ô có không quá một quân cờ. Đồng thời, phải thỏa mãn ~n~ điều kiện ràng buộc. Điều kiện thứ ~i~ của bài toán gồm hai số nguyên ~r_i~ và ~c_i~, có nghĩa là trong hình chữ nhật bao gồm các ô có tọa độ ~[1 \dots r_i] \times [1 \dots c_i]~ có không quá một quân cờ.

Yêu cầu: Hãy xác định số cách sắp xếp các quân cờ khác nhau thỏa mãn tất cả các ràng buộc, lấy theo modulo ~10^9 + 7~.

Input

• Dòng đầu tiên chứa các số nguyên ~n~ và ~m~, theo thứ tự là số lượng điều kiện hạn chế và kích thước bàn cờ ~(1 \le n \le 2 \cdot 10^5, 1 \le m \le 10^9)~.

• Tiếp theo là ~n~ dòng, mỗi dòng chứa hai số nguyên ~r_i~ và ~c_i~ ~(1 \le r_i, c_i \le m)~.

Output

Ghi ra một số nguyên duy nhất là số cách thỏa mãn yêu cầu bài toán, theo modulo ~10^9 + 7~.

Scoring

Sample Input 1

1 4
4 4

Sample Output 1

17

Sample Input 2

2 2
1 2
2 1

Sample Output 2

10

Sample Input 3

3 5
2 5
3 4
4 4

Sample Output 3

4480

Notes

Trong ví dụ đầu tiên, trên toàn bộ bàn cờ chỉ có thể đặt không quá một quân cờ. Có ~4 \times 4 = 16~ cách để đặt một quân cờ và ~1~ cách không đặt quân cờ nào. Suy ra có tổng cộng ~17~ cách.