問題文

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

制約

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

入力

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

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

出力

答えを出力せよ。

入力例 1

3
2 6 2

出力例 1

6

$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$ 通りの選び方が条件を満たします。

入力例 2

5
5 5 5 5 5

出力例 2

31

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