{"problem":{"name":"Avoid Permutations","description":{"content":"Let us consider the problem below for a permutation $P = (P_1, P_2, \\ldots, P_N)$ of $(1, 2, \\ldots, N)$, and denote the answer by $f(P)$. > We have an $(N+2)\\times (N+2)$ grid, where the rows are nu","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc118_e"},"statements":[{"statement_type":"Markdown","content":"Let us consider the problem below for a permutation $P = (P_1, P_2, \\ldots, P_N)$ of $(1, 2, \\ldots, N)$, and denote the answer by $f(P)$.\n\n> We have an $(N+2)\\times (N+2)$ grid, where the rows are numbered $0, 1, \\ldots, N+1$ from top to bottom and the columns are numbered $0, 1, \\ldots, N+1$ from left to right. Let $(i,j)$ denote the square at the $i$\\-th row and $j$\\-th column.\n> Consider paths from $(0, 0)$ to $(N+1, N+1)$ where we repeatedly move one square right or one square down. However, for each $1\\leq i\\leq N$, we must not visit the square $(i, P_i)$. How many such paths are there?\n\nYou are given a positive integer $N$ and an integer sequence $A = (A_1, A_2, \\ldots, A_N)$, where each $A_i$ is $-1$ or an integer between $1$ and $N$ (inclusive).\nConsider all permutations $P = (P_1, P_2, \\ldots, P_N)$ of $(1, 2, \\ldots, N)$ satisfying $A_i\\neq -1 \\implies P_i = A_i$. Find the sum of $f(P)$ over all such $P$, modulo $998244353$.\n\n## Constraints\n\n*   $1\\leq N\\leq 200$\n*   $A_i = -1$ or $1\\leq A_i\\leq N$.\n*   $A_i\\neq A_j$ if $A_i\\neq -1$ and $A_j\\neq -1$, for $i\\neq j$.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\ldots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc118_e","tags":[],"sample_group":[["4\n1 -1 4 -1","41\n\nWe want to find the sum of $f(P)$ over two permutations $P = (1,2,4,3)$ and $P = (1,3,4,2)$. The figure below shows the impassable squares for each of them, where `.` and `#` represent a passable and impassable square, respectively.\n\n  ......         ......\n  .#....         .#....\n  ..#...         ...#..\n  ....#.         ....#.\n  ...#..         ..#...\n  ......         ......\nP=(1,2,4,3)    P=(1,3,4,2)\n\n*   For $P = (1,2,4,3)$, we have $f(P) = 18$.\n*   For $P = (1,3,4,2)$, we have $f(P) = 23$.\n\nThe answer is the sum of them: $41$."],["4\n4 3 2 1","2\n\nIn this sample, we want to compute $f(P)$ for just one permutation $P = (4,3,2,1)$."],["3\n-1 -1 -1","48\n\n*   For $P = (1,2,3)$, we have $f(P) = 10$.\n*   For $P = (1,3,2)$, we have $f(P) = 6$.\n*   For $P = (2,1,3)$, we have $f(P) = 6$.\n*   For $P = (2,3,1)$, we have $f(P) = 12$.\n*   For $P = (3,1,2)$, we have $f(P) = 12$.\n*   For $P = (3,2,1)$, we have $f(P) = 2$.\n\nThe answer is the sum of them: $48$."]],"created_at":"2026-03-03 11:01:14"}}