D. Дима ба хоёр дараалал

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

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

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

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

Бяцхан Димад бүхэл тоон координаттай цэгүүдээс тогтсон $(a_{1}, 1), (a_{2}, 2), ..., (a_{n}, n)$ ба $(b_{1}, 1), (b_{2}, 2), ..., (b_{n}, n)$ гэсэн хоёр дараалал байна.

Дима эдгээр дарааллыг нэгтгэхийн хүссэн ба гэхдээ үүссэн $2n$ урттай дарааллын $x$ координатууд нь үл буурахаар эрэмбэлэгдсэн байх юм. Тэгээд дараа нь нийтдээ ийм байдлаар нэгтгэж болох хичнээн ялгаатай боломж байгааг мэдэхийг хүсчээ. Түүнд тусална уу. Анхны дарааллын элемент бүрийг нэгтгэсэн дараалалд нэг удаа л хэрэглэсэн байх ёстойг анхаараарай.

Хэрвээ $(p_{i}, q_{i}) ≠ (x_{i}, y_{i})$ байх $i$ $(1 ≤ i ≤ 2n)$ байдаг бол $(p_{1}, q_{1}), (p_{2}, q_{2}), ..., (p_{2n}, q_{2n})$ ба $(x_{1}, y_{1}), (x_{2}, y_{2}), ..., (x_{2n}, y_{2n})$ хоёр нэгтгэсэн дарааллуудыг ялгаатай гэж үзнэ.

Хариулт нь хэтэрхий том тоо байж болох тул хариуг $m$ тоонд хуваагаад гарсан үлдэгдлийг хэвлэнэ.

Оролт

Эхний мөр нь $n$ $(1 ≤ n ≤ 10^{5})$ бүхэл тоог агуулна. Хоёр дахь мөр нь $n$ ширхэг зайгаар тусгаарлагдсан $a_{1}, a_{2}, ..., a_{n}$ $(1 ≤ a_{i} ≤ 10^{9})$ бүхэл тоонуудыг агуулна. Гурав дахь мөр нь $n$ ширхэг зайгаар тусгаарлагдсан $b_{1}, b_{2}, ..., b_{n}$ $(1 ≤ b_{i} ≤ 10^{9})$ бүхэл тоонуудыг агуулна.

Сүүлийн мөрөнд нэг бүхэл тоо $m$ $(2 ≤ m ≤ 10^{9} + 7)$ байна.

Гаралт

Бодлогын хариуг $m$ тоонд хуваагаад гарсан үлдэгдлийг нэг мөрөнд хэвлэнэ.

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

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

Оролт
1
1
2
7
Гаралт
1
Оролт
2
1 2
2 3
11
Гаралт
2

Тэмдэглэл

Эхний жишээнд та зөвхөн нэг дараалал л гарган авч чадна: $(1, 1), (2, 1)$.

Хоёр дахь жишээнд та дараах дарааллуудыг гарган авч чадна:

  • $(1, 1), (2, 2), (2, 1), (3, 2)$
  • $(1, 1), (2, 1), (2, 2), (3, 2)$

Тиймээс хариулт нь $2$ байна.

Сэтгэгдлүүдийг ачааллаж байна...