E. Тоон хүснэгт

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

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

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

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

Энэ нь саяхан олдсон ба бүх Берландын одоогийн эдийн засгийн бүтэц нь энгийн $n × m$ хэмжээтэй хүснэгтээр дүрслэгдэж болно. $n$ -- Берландын сар болгонд байх өдрийн тоо, $m$ -- сарын тоог илэрхийлнэ. Түүнчлэн, хүснэгтийн нэг нүд нь Берландын жилийн нэг өдөр болон нэг сард харгалзах юм. Нүд болгонд $1$ эсвэл $-1$ байх ба энэ нь тухайн бүтцийн тодорхойлсон сарын тодорхойлсон өдрийн ашгийг илэрхийлнэ. $1$ нь орлогд харгалзах ба $-1$ нь зарлагд харгалзана. Энэ нь өмнөх жилийнхээ эдийн засгийн бүтцийн өгөгдөлд шинжлэл хийх амжилттай хөгжүүлэлтэд чухал байсан хэдий ч нярвууд өгөгдлийг буцаан авч архивлах үеэр уг хүснэгт нь ихээхэн хэмжээгээр гэмтжээ. Хүснэгтийн зарим нүднүүдийн тоон утга нь бүдгэрсэн ба тайлж унших боломжгүй болсон байв. Өгөгдлөө хадгалж үлдсэн нүднүүдийн тоо нь $max(n, m)$-ээс эрс бага болох нь мэдэгдэж байгаа юм. Тэгсэн хэдий ч, өөр нэмэлт мэдээлэл байгаа ба -- мөр болон багана тус бүрийн тоонуудын үржвэр нь $-1$-тэй тэнцүү байна. Таны даалгавар бол хадгалагдаж үлдсэн өгөгдлүүдтэй нийцэх хэчнээн ширхэг ялгаатай хүснэгтүүд байгааг олох юм. Даалгаврын хариулт нь маш том байж болох учраас, та үүнийг $p$ модулаар бодож олно уу.

Оролт

Эхний мөрөнд бүхэл тоонууд $n$ болон $m$ ($1 ≤ n, m ≤ 1000$) өгөгдөнө. 2-дахь мөрөнд бүхэл тоо $k$ ($0 ≤ k < max(n, m)$) өгөгдөнө -- энэ нь өгөгдлөө хадгалж үлдсэн нүднүүдийн тоог илэрхийлнэ. Дараагийн $k$ мөрөнд бүтцийн хүснэгт доторх хадгалагдаж үлдсэн нүднүүдийн өгөгдөл өгөгдөнө. Мөр бүр нь "$a$ $b$ $c$" хэлбэртэй байх ба энд $a$ ($1 ≤ a ≤ n$) -- хүснэгтийн мөрийн дугаар, $b$ ($1 ≤ b ≤ m$) -- хүснэгтийн баганын дугаар, $c$ -- нүдэнд агуулагдаж буй утгыг ($1$ эсвэл $-1$) илэрхийлнэ. Тэдгээр нь $1$-ээс эхлэн дугаарлагдсан байна. Мөн ижил $a$ болон $b$ утгуудтай 2 мөр оршин байхгүй. Сүүлийн мөрөнд бүхэл тоо $p$ ($2 ≤ p ≤ 10^{9} + 7$) өгөгдөнө.

Гаралт

Хадгалагдаж үлдсэн өгөгдлүүдтэй нийцэх ялгаатай хүснэгтүүдийн тоог $p$ модулаар бодож хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
2 2
0
100
Гаралт
2
Оролт
2 2
1
1 1 -1
100
Гаралт
1
Сэтгэгдлүүдийг ачааллаж байна...