Company: hackerrank_26thjune
Difficulty: hard
In a popular mobile game there is a “gacha” banner featuring N distinct collectible characters. Each time you make a pull you obtain exactly one character. The probability of obtaining the i -th character on any single pull is strictly proportional to a given weight W i : P_i = W_i / (W_1 + W_2 + ... + W_N) You are a completionist and will not stop pulling until you have collected at least one copy of every single character . Calculate the expected number of pulls you need to make to achieve this goal. The answer is a rational number p/q . Output it modulo 998244353 — that is, output (p · q −1 ) mod 998244353 , where q −1 is the modular multiplicative inverse of q . Input Format The first line contains a single integer N — the number of unique characters. The second line contains N integers W 1 , W 2 , …, W N — the weights of the characters. Output Format Output a single integer: the expected number of pulls required to obtain all