27632번 - Yet Another Sequence Related Problem 다국어

문제

There are two sequences of integers, $A_{1..N+M-1}$ and $B_{1..N}$. The sequence $B_{1..N}$ is obtained by aggregating the maximum value of every $M$ consecutive elements in $A,ドル or formally, $B_i = \max_{0≤j≤M−1}{A_{i+j}}$ for all $i = 1..N$.

Due to the COVID-19 pandemic, $A$ is completely lost. To make matters worse, zero or more elements in $B$ are also missing. Fortunately, you remember that each element in $A$ and $B$ are between 1ドル$ and $K$ (inclusive).

It doesn’t take you a long time to realize that there might be more than one possibility for an $A$ sequence that is consistent with the given $B$. Your task in this problem is to figure out how many such possible $A$ sequences are there if possible. Since the output can be very big, you only need to output its positive remainder when divided by 998ドル,244円,353円$.

입력

Input begins with a line containing three integers $N$ $M$ $K$ (1ドル ≤ N, M, K ≤ 100,000円$) representing the length of $B,ドル the number of consecutive elements in $A$ to make $B,ドル and the upper bound of any elements in $A,ドル respectively. The next line contains $N$ integers $B_i$ ($B_i ∈ \{-1, 1, 2, \dots , K\}$) representing the given sequence of $B$. Any missing element in $B$ is represented by $-1$.

출력

Output in a line an integer representing the number of possible $A$ modulo 998ドル,244円,353円$.

제한

힌트