Một công ty đang triển khai hệ thống gồm ~n~ cảm biến giám sát nhiệt độ dọc theo một con đường thẳng có độ dài ~2n~, các cảm biến được đánh thứ tự từ ~1~ đến ~n~. Cảm biến thứ ~i~ có phạm vi giám sát từ vị trí ~l_i~ đến vị trí ~r_i~ (~1 ≤ l_i < r_i ≤ 2n~), nghĩa là nó có thể đo nhiệt độ tại tất cả các điểm ~x~ sao cho ~l_i ≤ x ≤ r_i~, các mốc vị trí quản lý của tất cả các cảm biến đôi một khác nhau.

Do nhu cầu tiết kiệm năng lượng, trong mỗi ca giám sát, kỹ thuật viên chỉ bật một số cảm biến nhất định. Khi đó, vùng giám sát thực tế là hợp của tất cả các đoạn phạm vi đo của những cảm biến được bật. Các đoạn giám sát của các cảm biến được bật mà giao hoặc chạm nhau sẽ tạo thành một miền giám sát liên tục, hai đoạn cách nhau ít nhất một đơn vị sẽ được xem là hai miền liên thông riêng biệt. Số lượng các miền giám sát liên tục này phản ánh mức độ phân mảnh của vùng giám sát, và mức độ này sẽ làm tăng độ phức tạp giám sát của hệ thống. Độ phức tạp giám sát của một phương án bật cảm biến được tính bằng số miền giám sát liên tục nâng lên lũy thừa ~k~, với ~k~ là số nguyên cho trước.

Ví dụ: với hệ thống gồm ba cảm biến với phạm vi giám sát lần lượt là ~[1; 3]~, ~[2; 5]~, ~[4; 6]~ và ~k = 3~ thì:

• Với phương án bật từng cảm biến riêng thì mỗi phương án sẽ tạo được một miền giám sát liên tục nên độ phức tạp giám sát của các phương án này là ~1^3 = 1~.

• Với phương án bật cảm biến ~1~ và ~2~ hoặc bật cảm biến ~2~ và ~3~ thì sẽ tạo được một miền giám sát liên tục nên độ phức tạp giám sát của hai phương án này là ~1^3 = 1~.

• Với phương án bật cảm biến ~1~ và ~3~ thì sẽ tạo được hai miền giám sát liên tục nên độ phức tạp giám sát của phương án này là ~2^3 = 8~.

• Với phương án bật cả ba cảm biến thì sẽ tạo được một miền giám sát liên tục nên độ phức tạp của phương án này là ~1^3 = 1~.

Yêu cầu: Hãy tính tổng độ phức tạp của tất cả các phương án bật cảm biến khác rỗng.

INPUT

Dòng đầu chứa hai số nguyên dương ~n~ và ~k~.

~n~ dòng tiếp theo, dòng thứ i chứa hai số nguyên ~l_i~ và ~r_i~ (~l_i, r_i ≤ 2n~).

Ràng buộc dữ liệu vào: ~l_i ≠ l_j, r_i ≠ r_j~ (~i ≠ j; 1 ≤ i, j ≤ n~) và ~l_i ≠ r_j~ (~1 ≤ i, j ≤ n~).

OUTPUT

In ra một số là phần dư của kết quả tìm được khi chia cho ~1000000007~.

SUBTASKS

SAMPLE INPUT 1

3 3
1 3
2 5
4 6

SAMPLE OUTPUT 1

14

SAMPLE INPUT 2

4 2
5 7
2 3
1 4
6 8

SAMPLE OUTPUT 2

42