{"problem":{"name":"Cat Jumps","description":{"content":"You are given a sequence of positive integers $A_1,A_2,\\cdots,A_N$. Let $S=N+\\sum_{1 \\leq i \\leq N}A_i$. Cat Snuke has $S$ cards. Each card has an integer written on it. The integers on the cards are ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"wtf22_day2_d"},"statements":[{"statement_type":"Markdown","content":"You are given a sequence of positive integers $A_1,A_2,\\cdots,A_N$. Let $S=N+\\sum_{1 \\leq i \\leq N}A_i$.\nCat Snuke has $S$ cards. Each card has an integer written on it. The integers on the cards are $A_1,A_2,\\cdots,A_N,-1,\\cdots,-1$. Particularly, there are $\\sum_{1 \\leq i \\leq N}A_i$ cards with $-1$.\nSnuke is now standing at the coordinate $0$ on a number line. He will perform the following operation $S$ times.\n\n*   Let $x$ be the current coordinate of Snuke. Choose and discard one of the cards he has. Let $v$ be the number on the discarded card, and jump to the coordinate $x+v$. If he has jumped to the coordinate $0$, earn one coin.\n\nFor each $k=1,2,\\cdots,N$, find the number, modulo $998244353$, of sequences of moves for Snuke such that he earns exactly $k$ coins.\nNote that you should count sequences of moves. Namely, if two cards have the same number, discarding one of them is not distinguished from discarding the other.\n\n## Constraints\n\n*   $1 \\leq N \\leq 5000$\n*   $1 \\leq A_i \\leq 5000$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"wtf22_day2_d","tags":[],"sample_group":[["2\n1 1","2\n4\n\nOne possible sequence of moves is $(-1,+1,+1,-1)$. Here, Snuke changes his coordinate as $0 \\to -1 \\to 0 \\to 1 \\to 0$ and earns two coins.\nHere are all possible sequences of moves and the number of coins that will be earned.\n\n*   $(-1,-1,+1,+1)$: one coin\n*   $(-1,+1,-1,+1)$: two coins\n*   $(-1,+1,+1,-1)$: two coins\n*   $(+1,-1,-1,+1)$: two coins\n*   $(+1,-1,+1,-1)$: two coins\n*   $(+1,+1,-1,-1)$: one coin"],["3\n1 2 3","140\n220\n144"],["20\n16 6 15 19 1 9 6 1 11 7 6 12 3 11 11 18 10 9 15 5","507808441\n401798892\n110460932\n680359166\n737048635\n442374434\n737773176\n980506765\n473506608\n693729211\n532774651\n621434128\n4273369\n839437048\n585784927\n590354055\n969740008\n825216624\n442091194\n660636013"]],"created_at":"2026-03-03 11:01:14"}}