시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB0000.000%

## 문제

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$.

## 예제 입력 1

4 2 3
1 2 2 -1


## 예제 출력 1

6


There are $6$ possible sequences for $A$ that satisfy the given $B$.

• $1$ $1$ $2$ $1$ $1$
• $1$ $1$ $2$ $1$ $2$
• $1$ $1$ $2$ $1$ $3$
• $1$ $1$ $2$ $2$ $1$
• $1$ $1$ $2$ $2$ $2$
• $1$ $1$ $2$ $2$ $3$

## 예제 입력 2

5 4 6
3 5 2 -1 3


## 예제 출력 2

0


There is no possible sequence for $A$ that satisfies the given $B$. Perhaps there is something wrong with $B$, but it’s not your problem.

## 예제 입력 3

5 3 7
3 -1 -1 -1 5


## 예제 출력 3

8113