Description

The midterm exams are over. Rikka, who already feels there is nothing left to be afraid of, decided not to study math today, and started playing Yu-Gi-Oh! with Yuta.

“You have an empty hand and an empty field, and only 100 Life Points left. At this point, what can you still do?”

“Sore wa dou kana!”

“Nani?”

However, Rikka’s deck is really too weak. After analyzing it, Rikka found that within one turn, her deck cannot achieve an OTK, unless she has the protagonist’s luck:

Exodia the Forbidden One

—If you have this card in your hand, along with “Right Leg of the Forbidden One”, “Left Leg of the Forbidden One”, “Right Arm of the Forbidden One”, and “Left Arm of the Forbidden One”, you win the Duel.

But since Rikka is not a noble pay-to-win player, she is certain that among these five cards, at least one must be at the bottom of the deck. So Rikka is now facing a problem: she needs to draw the entire deck within one turn.

Rikka’s deck has a total of $m + 1$ cards. Because the last card is fixed, we only consider the first $m$ cards.

Among these $m$ cards, there are $n$ special cards and $m - n$ normal cards. Each special card has an attribute value $w_i$, meaning that after playing this card, she can draw another $w_i$ cards. Luckily, Rikka found that these cards satisfy $\sum\limits_{i=1}^n w_i = m$, so she can draw cards freely without worrying about deck-out.

Since these $m$ cards are shuffled, there are $m!$ different possible decks.

Now the turn begins. Rikka first draws one card from the deck, then she keeps playing cards from her hand. If she plays a special card, she can draw cards again, until she draws the last card and meets the win condition, or she runs out of cards in her hand, ends her turn, and thus loses the match.

For example, if the deck is $\{4,0,0,2,0,0,0\}$ (use $0$ to represent a normal card, and other numbers to represent $w_i$, where the last $0$ is the final piece), then Rikka’s play process can be:

• Draw one card, the cards in hand are $\{4\}$.
• Play $\{4\}$, then draw four cards, the cards in hand are $\{0,0,2,0\}$.
• Play $\{2\}$, and she still needs to draw two more cards. At this time she has already drawn the last piece, so Rikka wins.
• If the deck is $\{2,0,0,4,0,0,0\}$, it is not hard to see that Yuta wins.

Now, among these $m!$ different decks, Rikka wants to know how many of them allow her to win.

Input Format

The first line contains an integer $n$.

The second line contains $n$ space-separated positive integers $w_i$.

From the input you can compute $m = \sum w_i$.

Output Format

Output one integer representing the answer. The answer may be very large; you only need to output it modulo $998\,244\,353$.

1
5

24

6
1 2 3 4 5 6

90337303

Hint

Explanation for Sample $1$

Among all $m!$ possible decks, only the $24$ decks of the form $\{5,0,0,0,0,0\}$ satisfy the condition.

Constraints

For $10\%$ of the testdata, $m \leq 10$.

For $30\%$ of the testdata, $n \leq 8$.

For $50\%$ of the testdata, $n \leq 15$.

For $70\%$ of the testdata, $n \leq 30$.

For $100\%$ of the testdata, $n \leq 40$, $1 \leq w_i \leq 10^5$. It is also guaranteed that $m - n \geq 4$, because after all, the deck must contain these $5$ pieces.

Translated by ChatGPT 5