Özünə kömək et (Platin)

Бessinin n ədəd kəsiyi var. i-ci kəsik, l[i] ≤ x ≤ r[i] şərtini ödəyən bütün həqiqi x ədədlərini əhatə edir.

Kəsiklər dəstinin birləşməsi, ən azı bir kəsikdə olan bütün x ədədlərinin dəsti kimi müəyyən edilir. Kəsiklər dəstinin mürəkkəbliyi isə, onların birləşməsində təmsil olunan əlaqəli bölgələrin sayının k dərəcəsinə qaldırılmış halı kimi təyin olunur.

Bessi, bu n kəsik dəstinin bütün 2^n alt dəstələri üzrə mürəkkəbliklərin cəmini 10^9 + 7 moduluna görə hesablamaq istəyir.

Adətən sənin işin Bessiyə kömək etməkdir. Amma bu dəfə sən Bessisən və sənə kömək edəcək heç kim yoxdur. Özünə kömək et!

Giriş məlumatları

Birinci sətir n (1 ≤ n ≤ 10^5) və k (2 ≤ k ≤ 10) ədədlərini ehtiva edir. Növbəti n sətirin hər biri iki tam ədəd l[i] və r[i] ehtiva edir. l[i] < r[i] və bütün l[i], r[i] dəyərlərinin fərqli olduğu və 1..2n aralığında olduğu təmin edilir.

Çıxış məlumatları

Cavabı 10^9 + 7 moduluna görə çıxarın.

Nümunə

Hər bir boş olmayan alt dəstənin mürəkkəbliyi aşağıda verilmişdir.

{[1,6]} ⟹ 1, {[2,3]} ⟹ 1, {[4,5]} ⟹ 1

{[1,6],[2,3]} ⟹ 1, {[1,6],[4,5]} ⟹ 1, {[2,3],[4,5]} ⟹ 4

{[1,6],[2,3],[4,5]} ⟹ 1

Cavab 1 + 1 + 1 + 1 + 1 + 4 + 1 = 10.

Nümunələr