ガイジくんとガイズくんがゲームをしています。N個の石の山があり、各山にA_i個の石が存在します。ガイジくんから交互に、山を一つ選び、その山に存在する石を1個以上好きなだけ取り除くという操作をします。自分の手番で操作ができなくなった方が負けです。
二人はガイジなので当然最善の行動はせず、残っている山の中から一様ランダムに一つ山を選択し、山の石の残りをαとすると、1以上α以下の整数を一様ランダムに選んで石を取り除きます。
ガイジ君が勝つ確率は有理数で表せそうな気がするので、それをp/qとしたとき(pとqは互いに素)に、qx≡p (mod 998244353)を満たす0以上998244353未満の整数xを求めなさい。
N<=200000
A_i<=1000000000