TopCoder

User's AC Ratio

95.2% (20/21)

Submission's AC Ratio

49.0% (51/104)

Tags

Description

還記得聖誕節那天,Fysty 班上的 $N$ 個有兩隻手的學生(包含 Fysty 本人)要一起玩交換禮物,禮物和學生的編號都是 $1, 2, \ldots, N$。所有學生一開始都會抽一支籤,接著用左手拎著自己準備的禮物、右手拿著籤;其中,編號為 $i$ 的學員抽到了編號為 $p_i$ 的禮物。因為一些魔法,編號相同的禮物和籤之間會互相吸引,使得學生們像是手牽手般地圍成一個個溫馨的「小圈圈」(然而,在一些可悲的情況下,不幸的學生可能會抽到自己的禮物,然後用自己的左手牽右手,但這也是個小圈圈)。在這溫馨的氛圍中,Fysty 體察了一個難忘的性質:每個小圈圈的「組成人數」都互不相同。

事隔一個月後的今天,Fysty 才發現自己重要的隨身碟弄丟了,他想起自己一定是在聖誕節那天,和小圈圈的同學們聊天的時候遺失的。於是他今天早上製作了一份表單,想調查每個人是否還記得自己所屬的小圈圈的大小,試圖以此還原當天的情景片段。回覆結果中,學生 $i$ 的填答內容是 $a_i$。如果 $a_i = -1$,代表學生 $i$ 忘記自己所屬的小圈圈大小了;如果 $a_i > 0$ ,代表學生 $i$ 的印象中,他所屬的小圈圈大小為 $a_i$。Fysty 很好奇在滿足所有人的印象的情況下,有幾種可能的抽籤結果。你可以幫幫他嗎?

因為可能性或許會太多,請輸出可能的抽籤結果數除以 $998244353$ 的餘數。

Input Format

輸入的第一行包含一個正整數 $N$。
輸入的第二行包含 $N$ 個整數 $a_1, a_2, \ldots, a_N$。

  • $1 \le N \le 5000$
  • $a_i = -1$ 或 $1 \le a_i \le N$

Output Format

輸出「滿足所有學生們的印象的抽籤結果數」除以 $998244353$ 的餘數。兩種抽籤結果 $\langle p_i \rangle_{i = 1}^ {N} = \langle p_1, p_2, \ldots, p_N \rangle, \langle p_i' \rangle_{i = 1}^ {N} = \langle p_1', p_2', \ldots, p_N' \rangle$ 被視為不同的抽籤結果若存在一個 $1 \le i \le N$ 滿足 $p_i \neq p_i'$。

Sample Input 1

5
2 3 2 3 3

Sample Output 1

2

Sample Input 2

4
1 1 2 2

Sample Output 2

0

Sample Input 3

20
5 7 8 7 8 5 8 7 7 5 7 8 7 5 8 7 8 5 8 8

Sample Output 3

87091200

Sample Input 4

20
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

Sample Output 4

328902038

Sample Input 5

5
-1 -1 3 -1 2

Sample Output 5

6

Sample Input 6

5
2 -1 4 3 -1

Sample Output 6

0

Sample Input 7

4
2 -1 -1 2

Sample Output 7

0

Sample Input 8

20
-1 7 -1 7 -1 5 -1 -1 -1 5 7 -1 7 5 -1 7 -1 5 -1 -1

Sample Output 8

765900700

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~7 範例測資。 0
2 8~42 小班制:$N \leq 8$ 10
3 43~63 議論紛紛:$a_i \neq -1$ 20
4 64~83 集體失憶:$a_i = -1$ 20
5 0~94 順其自然:無額外限制。 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 5
1 1000 262144 65536 1 5
2 1000 262144 65536 1 5
3 1000 262144 65536 1 5
4 1000 262144 65536 1 5
5 1000 262144 65536 1 5
6 1000 262144 65536 1 5
7 1000 262144 65536 1 5
8 1000 262144 65536 2 5
9 1000 262144 65536 2 5
10 1000 262144 65536 2 5
11 1000 262144 65536 2 5
12 1000 262144 65536 2 5
13 1000 262144 65536 2 5
14 1000 262144 65536 2 5
15 1000 262144 65536 2 5
16 1000 262144 65536 2 5
17 1000 262144 65536 2 5
18 1000 262144 65536 2 5
19 1000 262144 65536 2 5
20 1000 262144 65536 2 5
21 1000 262144 65536 2 5
22 1000 262144 65536 2 5
23 1000 262144 65536 2 5
24 1000 262144 65536 2 5
25 1000 262144 65536 2 5
26 1000 262144 65536 2 5
27 1000 262144 65536 2 5
28 1000 262144 65536 2 5
29 1000 262144 65536 2 5
30 1000 262144 65536 2 5
31 1000 262144 65536 2 5
32 1000 262144 65536 2 5
33 1000 262144 65536 2 5
34 1000 262144 65536 2 5
35 1000 262144 65536 2 5
36 1000 262144 65536 2 5
37 1000 262144 65536 2 5
38 1000 262144 65536 2 5
39 1000 262144 65536 2 5
40 1000 262144 65536 2 5
41 1000 262144 65536 2 5
42 1000 262144 65536 2 5
43 1000 262144 65536 3 5
44 1000 262144 65536 3 5
45 1000 262144 65536 3 5
46 1000 262144 65536 3 5
47 1000 262144 65536 3 5
48 1000 262144 65536 3 5
49 1000 262144 65536 3 5
50 1000 262144 65536 3 5
51 1000 262144 65536 3 5
52 1000 262144 65536 3 5
53 1000 262144 65536 3 5
54 1000 262144 65536 3 5
55 1000 262144 65536 3 5
56 1000 262144 65536 3 5
57 1000 262144 65536 3 5
58 1000 262144 65536 3 5
59 1000 262144 65536 3 5
60 1000 262144 65536 3 5
61 1000 262144 65536 3 5
62 1000 262144 65536 3 5
63 1000 262144 65536 3 5
64 1000 262144 65536 4 5
65 1000 262144 65536 4 5
66 1000 262144 65536 4 5
67 1000 262144 65536 4 5
68 1000 262144 65536 4 5
69 1000 262144 65536 4 5
70 1000 262144 65536 4 5
71 1000 262144 65536 4 5
72 1000 262144 65536 4 5
73 1000 262144 65536 4 5
74 1000 262144 65536 4 5
75 1000 262144 65536 4 5
76 1000 262144 65536 4 5
77 1000 262144 65536 4 5
78 1000 262144 65536 4 5
79 1000 262144 65536 4 5
80 1000 262144 65536 4 5
81 1000 262144 65536 4 5
82 1000 262144 65536 4 5
83 1000 262144 65536 4 5
84 1000 262144 65536 5
85 1000 262144 65536 5
86 1000 262144 65536 5
87 1000 262144 65536 5
88 1000 262144 65536 5
89 1000 262144 65536 5
90 1000 262144 65536 5
91 1000 262144 65536 5
92 1000 262144 65536 5
93 1000 262144 65536 5
94 1000 262144 65536 5