İnəkçilik
Bessi ev tapşırığını inək təsərrüfatı üzrə təxirə salmışdı və indi sənin köməyinə ehtiyacı var! O, üç fərqli inək yemindən ibarət qarışıq yaratmalıdır. Lakin, bütün yaxşı inəklərin bildiyi kimi, bəzi inək yemləri bir-biri ilə qarışdırıla bilməz, əks halda partlayışa səbəb olarlar. Xüsusilə, a və b etiketli iki inək yemi yalnız a ⊕ b ≤ k olduqda eyni qarışıqda ola bilər.
QEYD. Burada a ⊕ b "bitwise xor" əməliyyatını, yəni a və b qeyri-mənfi tam ədədlərinin bitwise xor əməliyyatını ifadə edir. Bu əməliyyat hər bir uyğun bit cütlüyünü 2 əsasında toplamağa bərabərdir, lakin daşınma nəzərə alınmadan. Məsələn,
0 ⊕ 0 = 1 ⊕ 1 = 0,
1 ⊕ 0 = 0 ⊕ 1 = 1,
5 ⊕ 7 = 101[2] ⊕ 111[2] = 010[2] = 2
Bessinin n qutusu inək yemi var, i-ci qutu l[i]-dən r[i]-ə qədər olan yemləri ehtiva edir. Heç bir iki qutu ümumi inək yemlərinə malik deyil. O, neçə unikal üç fərqli inək yemi qarışığı yarada biləcəyini bilmək istəyir. Cavab çox böyük ola biləcəyi üçün onu 10^9 + 7 modulunda çıxarın.
Giriş Məlumatları
Birinci sətir iki tam ədəd n (1 ≤ n ≤ 2 * 10^4) və k (1 ≤ k ≤ 10^9) ehtiva edir. Növbəti n sətirin hər biri iki tam ədəd l[i] və r[i] (0 ≤ l[i] ≤ r[i] ≤ 10^9) ehtiva edir. Qutuların inək yemləri artan qaydada verilir; yəni, hər bir 1 ≤ i < n üçün r[i] < l[i+1] + 1.
Çıxış Məlumatları
Bessinin yarada biləcəyi üç fərqli yem qarışığının sayını 10^9 + 7 modulunda çıxarın.
Nümunə
Kimyəvi maddələri qarışdırmaq mümkün olmayan 13 qrupa bölə bilərik: (0...15), (16...31), ... (192...199). İlk on iki qrup hər biri 352 unikal qarışıq verəcək, sonuncu isə 56 (çünki (192 ... 199) aralığında olan üç fərqli qarışığın bütün C3_8 kombinasiyaları mümkündür), ümumilikdə 352 * 12 + 56 = 4280 qarışıq əldə edəcəyik.