Maşın öyrənməsi
В süni intellekt laboratoriyasında yeni bir maşın öyrənmə metodu hazırlanmışdır. Təlim proqramının öyrənmə prosesində n iterasiya istifadə olunur. Hər iterasiya, öyrənilən proqramın müəyyən bir təlim dəstində işə salınmasından ibarətdir.
0-dan k-ya qədər mürəkkəblikdə təlim dəstləri hazırlanmışdır. Təlim planı tam ədədlərdən ibarət olan [a[1], a[2], ..., a[n]] massivlə verilir, burada a[i] i-ci iterasiyada istifadə olunan dəstin mürəkkəbliyini göstərir. Bütün i üçün 1-dən n-ə qədər 0 ≤ a[i] ≤ k qeyri-bərabərliyi yerinə yetirilməlidir.
Məlum olmuşdur ki, təlim planının səmərəliliyi təlim dəstlərinin mürəkkəbliklərinin bit təsvirlərindən asılıdır. Planın səmərəli olması üçün 1 ≤ i < j ≤ n olan hər iki i və j üçün (a[i] and a[j]) = a[i] bərabərliyi yerinə yetirilməlidir. Xatırladaq ki, iki tam qeyri-mənfi ədədin bitwise "və" (and) əməliyyatı belə qurulmuşdur: hər iki ədədi ikilik sistemdə yazırıq, nəticənin i-ci ikilik rəqəmi 1-ə bərabərdir, əgər hər iki arqumentdə də o 1-ə bərabərdirsə. Məsələn, (14 and 7) = (1110[2] and 0111[2]) = 110[2] = 6. Bu əməliyyat bütün müasir proqramlaşdırma dillərində həyata keçirilir, C++, Java və Python dillərində "&" kimi, Pascalda isə "and" kimi yazılır.
Lakin eyni mürəkkəblikdə olan dəstlərin daimi istifadəsi öyrənmədə irəliləyiş vermir. Bunu qarşısını almaq üçün təlim planı aşağıdakı növ m tələblərə cavab verməlidir. Hər bir tələb iki ədəd l[i] və r[i] ilə verilir və a[li] ≠ a[ri] mənasını daşıyır. Laboratoriya əməkdaşları bütün tələblərə cavab verən səmərəli planların sayını tapmaq istəyirlər. Bu say çox böyük ola biləcəyi üçün, onu 10^9 + 7-yə bölünməsinin qalıqını tapmaq lazımdır.
Verilən tam ədədlər n və k, həmçinin l[i], r[i] növündə m tələblərə əsasən, bütün tələblərə cavab verən səmərəli planların sayını müəyyən edən və bu sayın 10^9 + 7-yə bölünməsinin qalıqını çıxaran proqram yazın.
Giriş məlumatları
Birinci sətir üç tam ədəd n, m və k (1 ≤ n ≤ 3 * 10^5, 0 ≤ m ≤ 3 * 10^5, 0 ≤ k ≤ 10^18) - təlim iterasiyalarının sayı, tələblərin sayı və təlim dəstinin maksimal mürəkkəbliyi.
Növbəti m sətir tələbləri təsvir edir, i-ci sətir iki tam ədəd l[i], r[i] ehtiva edir, bu da a[li] ≠ a[ri] mənasını daşıyır (1 ≤ l[i] < r[i] ≤ n). Bütün tələblərin fərqli olduğu təmin edilir.
Çıxış məlumatları
Bir tam ədəd çıxarın - bütün tələblərə cavab verən səmərəli planların sayının 10^9 + 7-yə bölünməsinin qalıqı.
İzah
Birinci test üçün bütün mümkün planlar: [0, 0], [0, 1], [0, 2], [0, 3], [1, 1], [1, 3], [2, 2], [2, 3], [3, 3].
İkinci test üçün: [0, 1, 1], [0, 2, 2].