{"problem":{"name":"Sum of CC","description":{"content":"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","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc187_b"},"statements":[{"statement_type":"Markdown","content":"For a sequence $A = (A_1, \\ldots, A_N)$ of length $N$, define $f(A)$ as follows.\n\n*   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.\n\nYou 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.\nBy 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$.\nFind the sum, modulo $998244353$, of $f(B')$ over all possible $B'$.\n\n## Constraints\n\n*   All input numbers are integers.\n*   $2 \\leq N \\leq 2000$\n*   $1 \\leq M \\leq 2000$\n*   Each $B_i$ is $-1$ or an integer between $1$ and $M$, inclusive.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$B_1$ $\\ldots$ $B_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc187_b","tags":[],"sample_group":[["3 3\n2 -1 1","6\n\nThere are three possible sequences $B'$: $(2,1,1)$, $(2,2,1)$, and $(2,3,1)$.\nWhen $B' = (2,1,1)$, an edge is drawn only between vertices $2$ and $3$, so the number of connected components is $2$. Thus, $f(B') = 2$.\nSimilarly, $f(B') = 2$ for $B' = (2,2,1)$ and $f(B') = 2$ for $B' = (2,3,1)$, so the answer is $2 + 2 + 2 = 6$."],["10 8\n-1 7 -1 -1 -1 2 -1 1 -1 2","329785"],["11 12\n-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1","529513150\n\nRemember to find the sum modulo $998244353$."]],"created_at":"2026-03-03 11:01:14"}}