问题描述

给定一个长度为$N$的正整数序列$A=(a_1,\ldots,a_N)$。共有$(2^N-1)$种方式选择$A$中的一个或多个元素。其中有多少种选择的平均值是整数？请将答案对$998244353$取模后输出。

约束条件

• $1 \leq N \leq 100$
• $1 \leq a_i \leq 10^9$
• 输入中的所有值都是整数。

输入

输入通过标准输入给出，格式如下：

N
a_1 ... 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$。