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

Мөөгөн одойнууд ямар ч тохиолдолд тарьсан мөөгнүүдээ дандаа жингээр нь өсөх дарааллаар нэг эгнээнд жагсаан суулгах дуртай. Тэгэхээр ... Эдгээр мөөгөн одойнууд энэхүү мөөгнүүдээ суулгачихаад юм идэхээр явдаг. $x$ минутын дараа эргэн ирж шинээр өссөн мөөгнүүдийг харангуутаа хүчээр өсөх дараалалд оруулна. Одойнууд бүх мөөгийг жингээр нь эрэмбэлж, өсөх дараалалд оруулан ахин суулгана. Тэгээд ахин юм идэхээр явнэ (эдгээр одойнууд үнэхээр их идэгчид байсан). Ахиад $y$ минутын дараа нийт жинг модул $p$ тоонд хуваахад хэд үлдэх вэ?

Оролт

Эхний мөр мөөгний тоо, анх суулгаснаас хойших хугацаа, хоёрдахь суулгалтаас хойших хугацаа, хуваах модулийн тоо болох $n$, $x$, $y$, $p$ ($1 ≤ n ≤ 10^6$, $0 ≤ x, y ≤ 10^{18}$, $x + y > 0$, $2 ≤ p ≤ 10^9$) дөрвөн бүхэл тоо өгөгднө. Дараагийн мөрөнд мөөгнүүдийн жин болох $n$ ширхэг $a_i$ бүхэл тоонууд үл буурах эрэмбээр агуулагдна ($0 ≤ a_i ≤ 10^9$).

Гаралт

Хариу нь $x + y$ минутын дараа мөөгнүүдийн нийт жинг модул $p$ тоонд хуваахад гарах ганц бүхэл тоог агуулна.