{"problem":{"name":"1 Loop Bubble Sort","description":{"content":"For a permutation $P = (P_1, \\ldots, P_N)$ of $(1, \\ldots, N)$, let $P' = (P'_1, \\ldots, P'_N)$ be the permutation obtained by performing the following operation once. *   For $i = 1, 2, \\ldots, N-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_c"},"statements":[{"statement_type":"Markdown","content":"For a permutation $P = (P_1, \\ldots, P_N)$ of $(1, \\ldots, N)$, let $P' = (P'_1, \\ldots, P'_N)$ be the permutation obtained by performing the following operation once.\n\n*   For $i = 1, 2, \\ldots, N-1$ in this order, if $P_i > P_{i+1}$, swap $P_i$ and $P_{i+1}$.\n\nYou are given a sequence $Q = (Q_1, \\ldots, Q_N)$ of length $N$. Each $Q_i$ is $-1$ or an integer between $1$ and $N$, inclusive.\nFind the number, modulo $998244353$, of permutations $P$ of $(1, \\ldots, N)$ such that, for every $i$, if $Q_i \\neq -1$ then $Q_i = P'_i$.\n\n## Constraints\n\n*   All input numbers are integers.\n*   $2 \\leq N \\leq 5000$\n*   Each $Q_i$ is $-1$ or an integer between $1$ and $N$.\n*   Each of $1,2,\\ldots,N$ appears at most once in $Q$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ \n$Q_1$ $\\ldots$ $Q_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc187_c","tags":[],"sample_group":[["4\n-1 -1 2 4","6\n\nFor example, $P = (3,1,4,2)$ satisfies the conditions. This can be confirmed by the following behavior of the operation.\n\n*   For $i=1$, since $P_1 > P_2$, swap $P_1$ and $P_2$, resulting in $P = (1,3,4,2)$.\n*   For $i=2$, since $P_2 < P_3$, do nothing.\n*   For $i=3$, since $P_3 > P_4$, swap $P_3$ and $P_4$, resulting in $P = (1,3,2,4)$.\n*   Thus, $P' = (1,3,2,4)$, satisfying $P'_3=2$ and $P'_4=4$.\n\nThere are six permutations $P$ that satisfy the conditions:\n\n*   $(1,3,4,2)$\n*   $(1,4,3,2)$\n*   $(3,1,4,2)$\n*   $(3,4,1,2)$\n*   $(4,1,3,2)$\n*   $(4,3,1,2)$"],["6\n-1 -1 -1 -1 2 -1","120"],["15\n-1 -1 -1 -1 -1 4 -1 -1 -1 -1 7 -1 -1 -1 -1","237554682\n\nRemember to find the count modulo $998244353$."]],"created_at":"2026-03-03 11:01:14"}}