2018 учебный год

(ИГО іріктемесі)

Ограничение по времени:

1 second

Ограничение по памяти:

32 megabytes

Төрт жыл сайын бүкіл елдер арасында <<Информатика бойынша Гладияторлық Олимпиадсы>> өтеді. Бұл сирек кездесетін жарыс, себебі қатысушыларға тек күшпен ғана жеңіп шығуға болмайды, соған қатар қатысушының ақылы жетік болуы керек. Берляндияда қазір бір жағымды қиындық туып отыр, олимпиадаға $N$ әр түрлі үміткерлер бар. Әр үміткердің зияткерлік деңгейін бір санмен бейнеледі, $i$-үміткердің зияткерлік деңгейі $i$-ге тең. Берляндия информатика бойынша күшті ел болғандықтан, олимпиадаға ел атынан кез-келген қатысушылар санын жіберуге болатыны мәлім. Алайда, оған қарамастан ел ішінде іріктеу жасамақшы. Іріктеу раундына бірнеше үміткер алынып, $M$ тур өткізіледі. $i$-турда осы операциялар орындалады:

1. Егер де осы турда ең болмаса $a_i$ үміткер болса, онда үміткерлердің ішінде ең төмеңгі деңгеймен $a_i$ үміткер кетеді. $i$-тур қайта жүргізіледі.
2. Егер де осы турда үміткерлер саны $a_i$ кіші болса, онда келесі турға барлық үміткерлер өтеді. $i=M$ болған жағдайда іріктеу аяқталады.

Іріктеуден кейінгі қалатын үміткерлер тізімі жалғыз екенін байқауға болады. Тілшілер барлық бола алатын жағдайларды қарастырып, барлық мүмкін бола алатын бастапқы үміткерлердің тізбегінен іріктеуден өткен үмірткерлердің тізбектерінің санын тапқылары келеді. Осы сан тым үлкен болғандықтан $P$ санына бөлгеннен кейінгі қалдығын шығарыңыз.

Формат входного файла

Бірінші жолда үш бүтін сан $M$, $N$ және $P$ ($1 \le M \le 1000$, $1 \le P, N \le 10^9$) — раундтар саны, үміткерлер саны және қалдық алуға арналған сан берілген. Ескертеміз, $P$ саны міндетті түрде жай сан болып келуі шарт емес. Келесі жолда $M$ бүтін сан $a_i$ ($1 \le a_i \le 1000$) — $i$-шы раундтың саны берілген.

Формат выходного файла

Бір сан — есептің жауабын шығарыңыз.

Система оценки

Есеп бес бөлімнен тұрады, әр бөлімде есепте берілген шектеулер орындалады:

1. $n \le 18$. $10$ ұпайға бағаланады.
2. $n \le 1000$. $18$ ұпайға бағаланады.
3. $n \le 10^6$, $P = 999999937$. $21$ ұпайға бағаланады.
4. Есепте берілген шектеулер. $51$ ұпайға бағаланады.

Пример:

Вход

3 4 100000
7 3 4

Ответ

17

( Aidos Nurmash )