{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 5000$\n*   $1 \\leq A_i \\leq 5000$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$"},{"iden":"sample input 1","content":"2\n1 1"},{"iden":"sample output 1","content":"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"},{"iden":"sample input 2","content":"3\n1 2 3"},{"iden":"sample output 2","content":"140\n220\n144"},{"iden":"sample input 3","content":"20\n16 6 15 19 1 9 6 1 11 7 6 12 3 11 11 18 10 9 15 5"},{"iden":"sample output 3","content":"507808441\n401798892\n110460932\n680359166\n737048635\n442374434\n737773176\n980506765\n473506608\n693729211\n532774651\n621434128\n4273369\n839437048\n585784927\n590354055\n969740008\n825216624\n442091194\n660636013"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}