Problem Statement

For a sequence $A = (A_1, \ldots, A_N)$ of length $N$, define $f(A)$ as follows.

• Prepare a graph with $N$ vertices labeled $1$ to $N$ and zero edges. For every integer pair $(i, j)$ satisfying $1 \leq i < j \leq N$, if $A_i \leq A_j$, draw a bidirectional edge connecting vertices $i$ and $j$. Define $f(A)$ as the number of connected components in the resulting graph.

You are given a sequence $B = (B_1, \ldots, B_N)$ of length $N$. Each element of $B$ is $-1$ or an integer between $1$ and $M$, inclusive.

By replacing every occurrence of $-1$ in $B$ with an integer between $1$ and $M$, one can obtain $M^q$ sequences $B'$, where $q$ is the number of $-1$ in $B$.

Find the sum, modulo $998244353$, of $f(B')$ over all possible $B'$.

Constraints

• All input numbers are integers.
• $2 \leq N \leq 2000$
• $1 \leq M \leq 2000$
• Each $B_i$ is $-1$ or an integer between $1$ and $M$, inclusive.

Input

The input is given from Standard Input in the following format:

N M
B_1 \ldots B_N

Output

Print the answer.