D. Цэцэгс

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

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

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

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

Тарвага болон сохор номин хоёр өглөөний хоолон дээрээ бяцхан тоглоом зохиожээ. Тарвага оройн хоолны үеэр бидний мэддэгээр цэцэг иднэ. Тэрээр оройн хоол бүрээр зөвхөн улаан болон цагаан цэцэгнүүд иднэ. Иймээс оройн хоолон дахь цэцэгнүүдийг дараалалд оруулж болно. Тэдний зарим нь улаан цэцэгс зарим хэсэг нь цагаан цэцэгс байна.

Гэвч оройн хоол амттай байлгах дүрэм байдаг: Тарвага цагаан цэцэгсээс $k$-аас ихгүй хэмжээтэйг идхийг хүсдэг.

Одоо тарвага $a$-аас $b$-ийн хооронд хэдэн аргаар цэцэгсийг идэж болохыг бодож байна. Нийт аргын тоо маш их байж болох тул $1000000007$ ($10^{9} + 7$) модулиар хэвлэнэ.

Оролт

Оролт нь хэд хэдэн тестээс бүрдэнэ.

Эхний мөрөнд хоёр бүхэл $t$ болон $k$ ($1 ≤ t, k ≤ 10^{5}$) тоонууд байна. $t$ нь тестийн тоог илэрхийлнэ.

Дараагийн $t$ мөрөнд хоёр бүхэл тоонууд байна. Жишээ нь: $a_{i}$ болон $b_{i}$ ($1 ≤ a_{i} ≤ b_{i} ≤ 10^{5}$) энд $i$-р тестийг тодорхойлов.

Гаралт

$t$ мөрөнд бүхэл тоонууд хэвлэнэ. $i$-р мөрөнд оройн хоолондоо тарвага $a_{i}$-ээс $b_{i}$-ийн хооронд хэдэн янзаар цэцэгсийг идэж болох боломжит тоог $1000000007$ ($10^{9} + 7$) модулиар гаргана.

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

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

Оролт
3 2
1 3
2 3
4 4
Гаралт
6
5
5

Тэмдэглэл

  • $k$=2 ба урт нь 1 үед тарвага ($R$) иднэ.
    • $k$=2 ба урт нь 2 үед тарвага ($RR$) ба ($WW$) иднэ.
    • $k$=2 ба урт нь 3 үед тарвага ($RRR$) ба ($RWW$),($WWR$) иднэ.
    • $k$=2 ба урт нь 4 үед тарвага ($WWWW$) эсвэл ($RWWR$), гэвч энэ жишээнд тэр ($WWWR$) идэж чадахгүй.
Сэтгэгдлүүдийг ачааллаж байна...