5330: Sample Game

Bob has a random number generator, it will generate x with probability p_x.
Now Bob will do the following operations:

• Step 1. Generate a number x by random number generator. 
• Step 2. If x is the largest number among the generated numbers (i.e.  x is no smaller than any previously generated numbers), go to step 1, otherwise, go to step 3. 
• Step 3. If Bob generates x numbers totally, Bob will get x² score. 

Now Bob wants to know the expected value of the score he will get.
If the answer is irreducible fraction x/y, you need to output an integer d in [0,998244352] which satisfies d * y mod 998244353=x mod 998244353.
It's guaranteed that y mod 998244353≠0.

The first line has one integers n, it means the random number generator can only generate integers in [1,n].
The second line has n positive integers w_1...n, it means p_i = w_i /（∑_j=1ⁿ  w_j）.
2≤n≤100，1≤w_i≤10⁶.

3
1 1 1

499122190