The midterm exams are over, and Rikka, feeling there is nothing left to fear, decides not to study mathematics today and starts playing Yu-Gi-Oh! with Yuta.

"You have no cards in your hand and no cards on the field, and your life points are only one hundred. What can you possibly do now?"

"Sore wa dou kana!"

"Nani?"

However, Rikka's deck is terrible. After analysis, Rikka realizes that she cannot achieve an OTK (One Turn Kill) with the cards in her deck unless she is blessed by the protagonist's aura:

Exodia the Forbidden One

—If you have this card, 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" in your hand, you win the duel.

But because Rikka is not a wealthy "pay-to-win" player, she is certain that one of these five cards is at the very bottom of the deck. Therefore, Rikka faces a difficult problem: she needs to draw through her entire deck in one turn.

Rikka's deck has a total of $m+1$ cards. Since 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$, which means that after playing this card, she can draw $w_i$ more cards. Fortunately, Rikka finds that these cards satisfy $\sum_{i=1}^n w_i=m$, so she can draw cards freely without worrying about exceeding the deck size.

Since these $m$ cards are shuffled, there are a total of $m!$ different possible deck configurations.

Now the turn begins. Rikka first draws one card from the deck, then continuously plays the cards in her hand. If she plays a special card, she can draw more cards until she draws the last card to achieve victory, or she runs out of cards in her hand, ending her turn and losing the duel.

For example, if the deck is $\{4,0,0,2,0,0,0\}$ (where $0$ represents a normal card and other numbers represent $w_i$, with the last $0$ being the final piece), Rikka's playing process could be:

1. Draw a card; the hand is $\{4\}$.
2. Play $\{4\}$, draw four more cards; the hand is $\{0,0,2,0\}$.
3. Play $\{2\}$, need to draw two more; at this point, the last piece is drawn, and Rikka wins.

If the deck is $\{2,0,0,4,0,0,0\}$, it is easy to see that Yuta wins.

Now, Rikka wants to know how many of these $m!$ different deck configurations allow her to win.

Input

The first line contains an integer $n$.

The second line contains $n$ positive integers $w_i$ separated by spaces.

From the input, you can calculate $m=\sum_{i=1}^n w_i$.

Output

Output an integer representing the answer. Since the answer may be very large, output the result modulo $998244353$.

Examples

Input 1

1
5

Output 1

24

Note 1

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

Input 2

6
1 2 3 4 5 6

Output 2

90337303

Input 3

See sample data download.

Input 4

See sample data download.

Constraints

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

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

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

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

For $100\%$ of the data, $n \leq 40$, $1 \leq w_i \leq 10^5$.

It is guaranteed that $m-n \geq 4$, as there must be these $5$ pieces in the deck.