Bob has a random number generator, it will generate with probability . 

Now Bob will do the following operations:

Step 1. Generate a number by random number generator.

Step 2. If is the largest number among the generated numbers (i.e., is no smaller than any previously generated numbers), go to step 1, otherwise, go to step 3.

Step 3. If Bob generates numbers totally, Bob will get score.

Now Bob wants to know the expected value of the score he will get.

If the answer is irreducible fraction , you need to output an integer in [0,998244352] which satisfies . It's guaranteed that .

The first line has one integers , it means the random number generator can only generate integers in .

The second line has  positive integers , it means .

.

.

Output the answer.

3
1 1 1

499122190