C. Цахилгаан шатаар явах

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

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

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

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

Та яг $n$ давхар барилгад байна гэж төсөөл. Давхруудын хооронд цахилгаан шатаар явж болдог ба давхрууд нь доороосоо дээш $1$-с $n$ хүртэл дугаарлагдсан гэж бодъё. Та одоо $a$-р давхарт байгаа бөгөөд их уйдсан байгаа, тиймээс цахилгаан шатанд суухаар шийдсэн. $b$-р давхарт орохыг хориглосон нууц лаборатори байдаг. Хэдий тийм ч та аль хэдийнээ шийдсэн ба цахилгаан шатаар $k$ үргэлжилсэн аялал хийхээр шийдсэн.

Та одоо $x$-р давхарт байгаа (эхлээд $a$ давхарт байсан) гэж бодъё. Өөр нэг аялал нь таны сонгосон ямар нэгэн $y$ ($y ≠ x$) давхруудын хооронд ба цахилгаан шат тэр давхар луу явна. Та нууц лаборатори байдаг $b$-р давхарлуу очиж болохгүй, мөн одоогийн байгаа $x$ давхраас таны сонгосон $y$ давхар хүрэх зай нь одоогийн байгаа $x$ давхраас нууц лаборатори байдаг $b$ давхар хүрэх зайнаас эрс бага байх ёстой гэж шийдсэн. Илүү тодорхой хэлвэл, энэ нь дараах тэнцэтгэл бишийг биелүүлэх ёстой гэсэн үг: $|x - y| < |x - b|$. Та цахилгаан шатаар амжилттай шилжсэнийхээ дараа $y$ тоог өөрийн тэмдэглэлийн дэвтэр дээрээ бичиж авна.

Таны даалгавар аяллын байж болох бүх ялгаатай боломжийн тоог олох юм. Аяллын нийт боломжийн тоо харьцангуй том байж болох учир олсон тоог $1000000007$ ($10^{9} + 7$) тоонд хувааж үлдэгдлийг авж болно.

Оролт

Нэг мөрөнд зайгаар тусгаарлагдсан $n$, $a$, $b$, $k$ ($2 ≤ n ≤ 5000$, $1 ≤ k ≤ 5000$, $1 ≤ a, b ≤ n$, $a ≠ b$) дөрвөн бүхэл тоо байна.

Гаралт

Нэг бүхэл тоо хэвлэнэ. Олсон тоог $1000000007$ ($10^{9} + 7$) тоонд хуваасан үлдэгдэл.

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

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

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

Тэмдэглэл

Хэрвээ $j$ ($1 ≤ j ≤ k$) бүхэл тоо ба $p_{j} ≠ q_{j}$ бол $p_{1}, p_{2}, ..., p_{k}$ ба $q_{1}, q_{2}, ..., q_{k}$ хоёр дарааллууд ялгаатай.

Жишээний тайлбар:

  1. Эхний жишээнд нэгдүгээр аялал нь $1$ болон $3$-р давхрын аль нэг дээр очиж болно, учир нь $|1 - 2| < |2 - 4|$ and $|3 - 2| < |2 - 4|$.
  2. Хоёр дахь жишээнд хоёр боломжит дараалал байна: $(1, 2)$; $(1, 3)$. Та эхний аяллаар $3$-р давхарт очиж болохгүй, учир нь энэ тохиолдолд хоёрдугаар аяллын давхар байхгүй.
  3. Гуравдугаар жишээнд хайсан дараалал байхгүй, учир нь эхний аяллаар сонгох давхар байхгүй.
Сэтгэгдлүүдийг ачааллаж байна...