E. Дима ба тоглоом

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Дима Аня хоёр янз бүрийн тоглоом тоглох дуртай. Одоо Дима Анятай хамт тоглох шинэ тоглоомын талаар бодож байна.

Дима цаасан дээр $n$ ширхэг хос $(l_{i}, r_{i})$ $(1 ≤ l_{i} < r_{i} ≤ p)$ бүхэл тоонуудыг бичив. Дараа нь тоглогчид ээлжээр нүүдэл хийнэ. Тухайн тоглогч өөрийн ээлжинд дараах үйлдлүүдийг хийж болно:

  1. $r_{i} - l_{i} > 2$ $(1 ≤ i ≤ n)$ байх нэг хос сонгоно.
  2. $i$-р буюу сонгосон хос тоог $(l_i + \lfloor \frac{r_i - l_i}{3} \rfloor, l_i + 2 \cdot \lfloor \frac{r_i - l_i}{3} \rfloor)$ хосоор, эсвэл $(l_i, r_i - \lfloor \frac{r_i - l_i}{3} \rfloor)$ хосоор солино. $⌊x⌋$ тэмдэглэгээ нь тооны бүхэл хэсгийг авах буюу хамгийн ойрын бага бүхэл тоо руу шилжүүлнэ гэсэн утгатай.

Цааш нүүдэл хийх боломжгүй болсон тоглогч хожигдоно.

Хоёр тоглогч үргэлж хамгийн зөв нүүдлийг хийж тоглосон тохиолдолд нэгдүгээр тоглогч ялдаг байхаар $n$ ширхэг $(l_{i}, r_{i})$ $(1 ≤ l_{i} < r_{i} ≤ p)$ бүхэл тоон хосуудыг олж бичихийг Дима хүсэж байлаа. Учир нь Дима эхний нүүдлийг хийх нэгдүгээр тоглогч учраас. Дима үүнийг хэдэн янзаар хийж чадах вэ. Хариултыг $1000000007$ $(10^{9} + 7)$ тоонд хуваагаад гарсан үлдэгдлийг хэвлэнэ үү.

Хэрвээ бичигдсэн хосуудын дараалал ялгаатай бол эдгээрийг ялгаатай тохиолдлууд гэж үзнэ.

Оролт

Эхний мөр нь $n$, $p$ $(1 ≤ n ≤ 1000, 1 ≤ p ≤ 10^{9})$ хоёр бүхэл тоог агуулна. Эдгээр тоонуудыг хооронд нь нэг зайгаар тусгаарлан бичнэ.

Гаралт

Бодлогын хариуг $1000000007$ $(10^{9} + 7)$ тоонд хуваагаад гарсан үлдэгдлийг нэг мөрөнд хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
2 2
Гаралт
0
Оролт
4 4
Гаралт
520
Оролт
100 1000
Гаралт
269568947
Сэтгэгдлүүдийг ачааллаж байна...