Алекс энэ жил маш сайн суралцсан бөгөөд далайн эрэг дээр байрлах Алушта хэмээх оюутны хотхон уруу аялах аяллын эрх хожжээ.

Харамсалтай нь одоо маш хүчтэй салхилдаг үе бөгөөд уг оюутны хотхон нь нурсан байх магадлалтай ажээ! Оюутны хотхоны барилга нь $n + 2$ ширхэг цементэн блок өндөртэй, $m$ ширхэг блок өргөнтэй тэгш өнцөгтөөр дүрслэгддэг байв.

Өдөр болгон далайн эргээс хүчтэй салхи үлээх бөгөөд дээд болон доод бэхэлгээнд байрлах 2 урт блокноос бусад зүүн талдаа ямар ч блокгүй бүх блокууд нь магадлалаар устах ажээ. Мөн ижлээр шөнө болгон далайн эрэг уруу хүчтэй салхи үлээх бөгөөд дээд болон доод бэхэлгээнд байрлах 2 урт блокноос бусад баруун талдаа ямар ч блокгүй бүх блокууд нь мөн адил $p$ магадлалаар устах ажээ. Дээд болон доод бэхэлгээнд байрлах 2 урт блок нь яаж ч байсан устахгүй учраас нийт устаж болох $n*m$ ширхэг блок байгааг анхаарна уу.

Хүчтэй салхины үе нь $k$ өдөр $k$ шөнө үргэлжлэх юм. Хэрэв уг хугацааны туршид оюутны хотхон нь дор хаяж 2 ширхэг холбогдсон бүрэлдэхүүн хэсгүүдэд хуваагдах бол уг байрыг нурна гэж үзэх бөгөөд Алекс зуныг өнгөрөөх өөр газар хайх хэрэгтэй болох юм.

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

Оролт

Оролтын эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ ($1 ≤ n, m ≤ 1500$) өгөгдөх ба эдгээр нь уг оюутны хотхоны устаж болох хэсгийн хэмжээг илэрхийлнэ.

2-дахь мөрөнд 2 бүхэл тоо $a$ болон $b$ ($1 ≤ a ≤ b ≤ 10^{9}$) өгөгдөх ба эдгээр нь $p$ магадлалын утгыг илэрхийлэх юм. Түүнчлэн $a$ болон $b$ нь харилцан анхны тоонууд байна.

3-дахь мөрөнд ганц бүхэл тоо $k$ ($0 ≤ k ≤ 100 000$) өгөгдөх ба энэ нь хүчтэй салхины үе үргэлжлэх өдөр болон шөнийн тоог илэрхийлнэ.

Гаралт

Хариултыг -тай тэнцүү үл хураагдах бутархай гэж үзье. Тэгвэл -тай тэнцүү байх ганц бүхэл тоо хэвлэнэ үү. Мөн энэ нь гэсэн нөхцөлтэй байх юм.

Эхний жишээн дээр эдгээр 4 блок тус бүр нь магадлалтайгаар устах юм. Нийт $7$ ширхэг тохиолдлын хувьд уг оюутны хотхон нь нурахгүй байх бөгөөд иймд бидний хайж буй магадлал нь -тай тэнцүү болно. Иймд та гэж хэвлэх юм.