题目描述

给定一个长度为 $N$ 的正整数序列 $A=(a_1, \ldots, a_N)$。
从 $A$ 中选择一个或多个数的方式共有 $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$ 中的一个或多个数，平均值始终为 $5$。