题目描述

给你一个长为 $N$ 的正整数序列$A=(a1,…,aN),$ 从 A中选一项或多项有$2^{N}-1$ 种方式。其中有多少种方式满足所选的数的平均数是整数？ 求出这个数目除以 998244353的余数。

输入格式

第一行输入一个正整数N 第二行输入 $(a1,…,aN),$，表示这个正整数序列

输出格式

输出合理的方案数

3
2 6 2

6

5
5 5 5 5 5

31

提示

$1 \le N \le 100$

$1 \le a_i \le 10^{9}$