AT_abc313_g [ABC313G] Redistribution of Piles

管理备注：atcoder library 提供计算 $\sum\limits_i\left\lfloor\dfrac{ai+b}{c}\right\rfloor$ 的函数，使得本题使用和不使用 atcoder library 的难度相差过大，故本题评灰。

[problemUrl]: https://atcoder.jp/contests/abc313/tasks/abc313_g $ 1 $ から $ N $ までの番号がついた $ N $ 枚の皿があります。皿 $ i $ には $ a_i $ 個の石が載っています。また、空の袋があります。 あなたは以下の 2 種類の操作を好きな順番で 0 回以上何度でも行うことができます。 - 石が $ 1 $ 個以上載っている皿全てから石を $ 1 $ 個ずつ取る。取った石は袋に移動する。 - 袋から石を $ N $ 個取り出し、全ての皿に $ 1 $ 個ずつ石を載せる。ただし、この操作は袋に石が $ N $ 個以上ある場合にのみ行うことができる。 操作後に皿 $ i $ に載っている石の個数を $ b_i $ とします。$ b_i $ を並べてできる長さ $ N $ の整数列 $ (b_1,\ b_2,\ \dots,\ b_N) $ としてあり得るものの個数を $ 998244353 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ a_2 $ $ \dots $ $ a_N $

$ (b_1,\ b_2,\ \dots,\ b_N) $ としてあり得るものの個数を $ 998244353 $ で割った余りを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 0\ \leq\ a_i\ \leq\ 10^9 $ ### Sample Explanation 1 例えば以下の手順で操作を行うと $ b $ は $ (2,\ 1,\ 2) $ になります。 - 1 番目の操作を行う。$ b $ は $ (2,\ 0,\ 2) $ になる。 - 1 番目の操作を行う。$ b $ は $ (1,\ 0,\ 1) $ になる。 - 2 番目の操作を行う。$ b $ は $ (2,\ 1,\ 2) $ になる。 操作後の $ b $ としてあり得る列は次の $ 7 $ 種類です。 - $ (0,\ 0,\ 0) $ - $ (1,\ 0,\ 1) $ - $ (1,\ 1,\ 1) $ - $ (2,\ 0,\ 2) $ - $ (2,\ 1,\ 2) $ - $ (2,\ 2,\ 2) $ - $ (3,\ 1,\ 3) $ ### Sample Explanation 2 操作後の $ b $ としてあり得るものは $ (0) $ の $ 1 $ 種類です。