Giúp Chính Mình

Cho $N$ đoạn thẳng trên trục số, đoạn $i$ từ $l_i$ đến $r_i$. Mọi đầu mút $l_i$, $r_i$ đều phân biệt và nằm trong $[1,2N]$.

Với mỗi tập con $S$ của $N$ đoạn, định nghĩa độ phức tạp $c(S)$ là số thành phần liên thông trong hợp của các đoạn trong $S$ (tập rỗng có độ phức tạp 0).

Tính ${\displaystyle {\sum }_{S\subseteq \{1,\dots ,N\}}c(S{)}^K(\mathrm{mod}{10}^9+7)}$.

Dữ liệu vào

• Dòng 1: hai số nguyên $N$ và $K$ ($1\le N\le {10}^5$, $2\le K\le 10$)
• $N$ dòng tiếp theo: mỗi dòng hai số $l_i$ và $r_i$ ($l_i<r_i$)

Dữ liệu ra

In ra đáp án modulo ${10}^9+7$.

Ràng buộc

• $1\le N\le {10}^5$, $2\le K\le 10$
• Mọi $2N$ đầu mút đều phân biệt, thuộc $[1,2N]$

Ví dụ