我讨厌非整数

题目描述

给定一个长度为 $N$ 的正整数数列 $A=(a_1,\ldots,a_N)$。

从 $A$ 中选出非空子序列共有 $(2^N-1)$ 种方式。其中，所选元素的平均值为整数的选法有多少种？请将答案对 $998244353$ 取模后输出。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出答案。

样例

3
2 6 2

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$ 种选法满足条件。

5
5 5 5 5 5

31

无论怎样选择 $A$ 的非空子序列，平均值都等于 $5$。

数据范围

• $1 \le N \le 100$
• $1 \le a_i \le 10^9$
• 输入均为整数