Bessie được cho \(N\) đoạn thẳng (\(1\le N\le 10^5\)) trên một trục số một chiều. Đoạn thẳng thứ \(i\) chứa mọi số thực \(x\) thỏa mãn \(l_i\le x\le r_i\).

Định nghĩa hợp của một tập các đoạn thẳng là tập hợp mọi \(x\) nằm trong ít nhất một đoạn thẳng. Định nghĩa độ phức tạp của một tập các đoạn thẳng là lũy thừa bậc \(K\) của số miền liên thông được biểu diễn trong hợp của chúng (\(2\le K\le 10\)).

Bessie muốn tính tổng độ phức tạp trên tất cả \(2^N\) tập con của tập \(N\) đoạn thẳng đã cho, lấy phần dư theo \(10^9+7\).

Thông thường, nhiệm vụ của bạn là giúp Bessie. Nhưng lần này, bạn chính là Bessie và không có ai giúp bạn. Hãy tự giúp mình!

Phân nhóm

• Test 2 thỏa mãn \(N\le 16\).
• Các test 3-5 thỏa mãn \(N\le 1000\), \(K=2\).
• Các test 6-8 thỏa mãn \(N\le 1000\).
• Với mỗi \(T\in[9,16]\), test \(T\) thỏa mãn \(K=3+(T-9)\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(K\).

Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(l_i\) và \(r_i\). Dữ liệu bảo đảm \(l_i<r_i\) và tất cả các giá trị \(l_i,r_i\) là những số nguyên đôi một phân biệt thuộc đoạn \(1\ldots 2N\).

Dữ liệu ra

In đáp án lấy phần dư theo \(10^9+7\).

Ví dụ

3 2
1 6
2 3
4 5

10

Nguồn

USACO 2020 February Contest, Platinum - Help Yourself: https://usaco.org/index.php?page=viewproblem2&cpid=1022

Tác giả: Benjamin Qi.