题目描述

項数が $N$ の正整数列 $A=(a_1,\ldots,a_N)$ が与えられます。
$A$ の項を $1$ 個以上選ぶ方法は $2^N-1$ 通りありますが、そのうち選んだ項の平均値が整数であるものが何通りかを $998244353$ で割った余りを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $a_1$ $\ldots$ $a_N$

输出格式

答えを出力せよ。

题目大意

已知一个长度为 $N$ 的数列 $a_1,a_2,\cdots a_N$，从数列中选出至少一个数，使选出的数平均数为整数，求有多少种这样的方案。

3
2 6 2

6

5
5 5 5 5 5

31

提示

制約

• $1\ \leq\ N\ \leq\ 100$
• $1\ \leq\ a_i\ \leq\ 10^9$
• 入力はすべて整数

Sample Explanation 1

$A$ の項を選ぶ方法それぞれに対する平均値は以下のようになります。 - $a_1$ のみを選んだ場合、平均値は $\frac{a_1}{1}=\frac{2}{1}\ =\ 2$ であり、整数である。 - $a_2$ のみを選んだ場合、平均値は $\frac{a_2}{1}=\frac{6}{1}\ =\ 6$ であり、整数である。 - $a_3$ のみを選んだ場合、平均値は $\frac{a_3}{1}=\frac{2}{1}\ =\ 2$ であり、整数である。 - $a_1$ と $a_2$ を選んだ場合、平均値は $\frac{a_1+a_2}{2}=\frac{2+6}{2}\ =\ 4$ であり、整数である。 - $a_1$ と $a_3$ を選んだ場合、平均値は $\frac{a_1+a_3}{2}=\frac{2+2}{2}\ =\ 2$ であり、整数である。 - $a_2$ と $a_3$ を選んだ場合、平均値は $\frac{a_2+a_3}{2}=\frac{6+2}{2}\ =\ 4$ であり、整数である。 - $a_1$ と $a_2$ と $a_3$ を選んだ場合、平均値は $ \frac{a_1+a_2+a_3}{3}=\frac{2+6+2}{3}\ =\ \frac{10}{3} $ であり、整数ではない。 以上より、$6$ 通りの選び方が条件を満たします。

Sample Explanation 2

どのように $A$ の項を $1$ 個以上選んでも平均値が $5$ になります。