Бауырсақ жарысы

Ұпайлар: 0

Уақыт шектеуі: 1.0s

Жад шектеуі: 256M

Problem types

Жақында спортты түрде бауырсақ жеуден Ваута жарысы өтті. Жарыста $n$ адам қатысты. Тіркелу кезінде ұйымдастырушылар әр қатысушыға $1$ ден $n$-ге дейін бірегей нөмір берді. Ережелер оңай: кім көбірек бауырсақ жесе, сол ұтады. Жарыстың қорытындысы бойынша $n$ бағаннан тұратын кесте құрылады. Кестенің әр бағанында қатысушының орны мен оның аты жазылған. Егер екі қатысушы бірдей бауырсақ санын жеген болса, олардың орны кестесе бірдей болып белгіленеді және есімдерінің реті бойынша орналасады (барлық қатысушының есімдері әртүрлі деп есептейік). Мысалға, $n = 5$ болса, және Темірлан мен Батыр $100$ бауырсақ, Тима $99$ бауырсақ, ал Айдос пен Әлімжан $98$ бауырсақ жеген болса, кесте келесідей болады:

1. Батыр

1. Темірлан

3. Тима

4. Айдос

4. Алимжан

Әр адам үшін оның кестедегі қорытынды орнын $p$ жиымында жазып алды. Нөмірі $i$ болатын адам $p_i$ орнын алды. Алайда, орындарды маркермен жазып алғаннан соң кейбір мәндер өшіп қалды. Енді сізден қанша әртүрлі қорытынды кесте болуы мүмкін екенін сұрап жатыр.

Input

Бірінші жолда қатысушылар саны $n$ $(1 \le n \le 5000)$ берілген.

Екінші жолда $n$ бүтін сан $p_1, \ldots, p_n$ берілген $(0 \le p_i \le n)$ — нөмірі $i$ болатын қатысушының орны немесе орны белгісіз болса $0$ мәні.

Output

Бір бүтін сан шығарыңыз — берілген мәндерге сәйкес келетін қорытынды кестелердің саны. Жауап өте болуы мүмкін болатындықтан, жауаптың $998244353$ санына бөлгендегі қалдығын шығарыңыз.

Sample Input 1

3
0 1 3

Sample Output 1

Sample Input 2

3
3 3 3

Sample Output 2

Sample Input 3

5
0 0 0 0 0

Sample Output 3

Notes

Екі кесте әртүрлі болып саналады, егер олар әртүрлі болатын баған табылса.

Бірінші мысалда мүмкін опциялар: $2\ 1\ 3$ және $1\ 1\ 3$. Мысалы, $3\ 1\ 3$ опциясы мүмкін емес, өйткені ол екінші орынды жіберіп алады.

Пікірлер

0

alimzhan пікір қалдырды Ақп. 11, 2024, 6:08 Т.Ж.

Добавлено объяснение к примеру.

0

alimzhan пікір қалдырды Ақп. 11, 2024, 5:16 Т.Ж.

Правильная нумерация в условии:

1 Батыр

1 Темирлан

3 Тима

4 Айдос

4 Алимжан