/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 466 点
問題文
高橋君は 1 から N までの番号が付いた N 個のボールを、ボール 1, ボール 2, \dots, ボール N の順に、1 から M までの番号が付いた M 個の箱のいずれかに入れていく。1 つの箱には何個でもボールを入れることができる。ボール i を入れた箱の番号を B_i とする（1 \leq B_i \leq M）。
青木君は、箱番号列 B_1, B_2, \dots, B_N を次の手続きで「圧縮番号列」 C_1, C_2, \dots, C_N に変換して記録した。この手続きは、箱番号の出現順に 1, 2, 3, \dots と新しい番号を割り当てるものである。
> はじめ、どの箱番号にも圧縮番号は割り当てられていない。
>
> i = 1, 2, \dots, N の順に以下を行う。
> - 箱番号 B_i にまだ圧縮番号が割り当てられていない場合（すなわち B_i が B_1, B_2, \dots, B_{i-1} のいずれとも異なる場合）、箱番号 B_i に対して、まだどの箱番号にも割り当てられていない最小の正整数を圧縮番号として割り当てる。C_i をその圧縮番号とする。
> - 箱番号 B_i にすでに圧縮番号が割り当てられている場合（すなわち B_1, B_2, \dots, B_{i-1} の中に B_i と等しいものが存在する場合）、C_i を、箱番号 B_i に割り当て済みの圧縮番号とする。
例えば、箱番号列が (5, 5, 2, 7, 2) のとき、箱番号 5 に圧縮番号 1、箱番号 2 に圧縮番号 2、箱番号 7 に圧縮番号 3 が割り当てられ、圧縮番号列は (1, 1, 2, 3, 2) となる。
ところが、記録の一部が汚れて読めなくなってしまった。
長さ N の列 D_1, D_2, \dots, D_N が与えられる。D_i = 0 のとき C_i の値は不明であり、D_i \neq 0 のとき C_i = D_i でなければならない。
箱番号列 B_1, B_2, \dots, B_N（各 B_i は 1 以上 M 以下の整数）であって、上の手続きで得られる圧縮番号列 C_1, C_2, \dots, C_N が D の条件を全て満たすものの個数を、998244353 で割った余りを求めよ。ここで、2 つの箱番号列は、ある i が存在して B_i の値が異なるとき区別する。条件を満たす箱番号列が存在しない場合は 0 を出力せよ。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- N \times \min(N, M) \leq 2.5 \times 10^7
- 0 \leq D_i \leq N
- 入力はすべて整数である
入力
N M D_1 D_2 \dots D_N
- 1 行目には、ボールの個数 N と、箱の番号の最大値 M が、スペース区切りで与えられる。
- 2 行目には、一部が不明になった圧縮番号列を表す D_1, D_2, \dots, D_N が、スペース区切りで与えられる。
- D_i = 0 のとき、i 番目の圧縮番号は不明であることを表す。
- D_i \geq 1 のとき、i 番目の圧縮番号が D_i であることを表す。
出力
条件を満たす箱番号列の個数を 998244353 で割った余りを 1 行で出力せよ。
入力例 1
5 4 1 1 2 0 2
出力例 1
48
入力例 2
4 2 1 2 3 0
出力例 2
0
入力例 3
10 6 1 0 2 0 2 3 0 1 4 0
出力例 3
51840
入力例 4
24 15 1 0 2 0 3 0 1 4 0 2 5 0 0 3 6 0 4 0 6 7 0 5 0 7
出力例 4
280519446
入力例 5
1 1 0
出力例 5
1
Score : 466 pts
Problem Statement
Takahashi places N balls numbered from 1 to N into some of M boxes numbered from 1 to M, in the order of ball 1, ball 2, \dots, ball N. Each box can hold any number of balls. Let B_i denote the box number in which ball i is placed (1 \leq B_i \leq M).
Aoki recorded the box number sequence B_1, B_2, \dots, B_N by converting it into a "compressed number sequence" C_1, C_2, \dots, C_N using the following procedure. This procedure assigns new numbers 1, 2, 3, \dots in the order of first appearance of each box number.
> Initially, no box number has a compressed number assigned to it.
>
> For i = 1, 2, \dots, N in order, do the following:
> - If box number B_i has not yet been assigned a compressed number (i.e., B_i is different from all of B_1, B_2, \dots, B_{i-1}), assign to box number B_i the smallest positive integer not yet assigned to any box number as its compressed number. Set C_i to that compressed number.
> - If box number B_i has already been assigned a compressed number (i.e., there exists some element among B_1, B_2, \dots, B_{i-1} equal to B_i), set C_i to the compressed number already assigned to box number B_i.
For example, when the box number sequence is (5, 5, 2, 7, 2), box number 5 is assigned compressed number 1, box number 2 is assigned compressed number 2, and box number 7 is assigned compressed number 3, resulting in the compressed number sequence (1, 1, 2, 3, 2).
However, part of the record became dirty and unreadable.
You are given a sequence D_1, D_2, \dots, D_N of length N. When D_i = 0, the value of C_i is unknown. When D_i \neq 0, it must hold that C_i = D_i.
Find the number of box number sequences B_1, B_2, \dots, B_N (where each B_i is an integer between 1 and M inclusive) such that the compressed number sequence C_1, C_2, \dots, C_N obtained by the above procedure satisfies all the conditions of D, modulo 998244353. Here, two box number sequences are considered distinct if there exists some i such that their values of B_i differ. If no valid box number sequence exists, output 0.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- N \times \min(N, M) \leq 2.5 \times 10^7
- 0 \leq D_i \leq N
- All input values are integers.
Input
N M D_1 D_2 \dots D_N
- The first line contains the number of balls N and the maximum box number M, separated by a space.
- The second line contains D_1, D_2, \dots, D_N, representing the partially unknown compressed number sequence, separated by spaces.
- When D_i = 0, it means the i-th compressed number is unknown.
- When D_i \geq 1, it means the i-th compressed number is D_i.
Output
Output the number of valid box number sequences modulo 998244353 in a single line.
Sample Input 1
5 4 1 1 2 0 2
Sample Output 1
48
Sample Input 2
4 2 1 2 3 0
Sample Output 2
0
Sample Input 3
10 6 1 0 2 0 2 3 0 1 4 0
Sample Output 3
51840
Sample Input 4
24 15 1 0 2 0 3 0 1 4 0 2 5 0 0 3 6 0 4 0 6 7 0 5 0 7
Sample Output 4
280519446
Sample Input 5
1 1 0
Sample Output 5
1