Last Hunter Standing

This problem is based on a folk version of the popular game Werewolf, called Hunter Kill. Initially there are \(n\) hunters, where the \(i\)th hunter has a hatred level \(w_i\). Each hunter possesses a unique skill: upon death they must fire a single shot, and whoever is hit will also die. This triggers a chain reaction until all hunters have perished.

The process is as follows:

1. The very first shot is fired by an external agent (you). The target is selected among all \(n\) hunters with probability proportional to their hatred levels, i.e. the \(i\)th hunter is chosen with probability \(\frac{w_i}{\sum_{j=1}^{n}w_j}\).
2. Once a hunter is killed, he immediately fires his shot. If the current set of alive hunters is \(\{i_1, i_2, \ldots, i_m\}\), then he chooses hunter \(i_k\) with probability \(\frac{w_{i_k}}{\sum_{j=1}^{m} w_{i_j}}\) causing that hunter to die.
3. This chain reaction continues until no hunter remains alive. Note that every hunter (except one) gets to shoot exactly once upon death.

Your task is to calculate, modulo \(998244353\), the probability that hunter \(1\) is the last one to die.

Note: All probabilities in the process are defined in the weighted manner described above. It can be shown that, regardless of the order in which the shots occur, eventually all hunters will die.

inputFormat

The input begins with an integer \(n\) (\(1 \leq n \leq 20\)), representing the number of hunters. The next line contains \(n\) space-separated integers \(w_1, w_2, \ldots, w_n\) (each \(w_i\) is a positive integer) denoting the hatred level of each hunter.

It is guaranteed that the parameters are such that a bitmask dynamic programming solution is feasible.

outputFormat

Output a single integer, the probability that hunter \(1\) is the last to die, modulo \(998244353\).

sample

1
5

1