题目背景

n个数组成的集合中有多少种集合的平均值为整数？

题目描述

给你一个长度为 $N$ 的正整数序列 $a_1,a_2...a_n$ 。

有 $(2^N-1)$ 种方法可以选择 $a$ 中的若干个数组成一个集合。其中有多少种选数方案的平均值是整数？

求方案数对 $998244353$ 取模的结果。

输入格式

第一行输入包含一个整数 $n$ ( $1\leq n\leq 100$ )，表示 $a$ 数组的长度。

第二行输入 $n$ 个整数表示 $a$ 数组（$1\le a_i\le 10^9$）。

输出格式

输出方案数，对 $998244353$ 取模。

输入输出样例 #1

输入 #1

3
2 6 2

输出 #1

6

输入输出样例 #2

输入 #2

5
5 5 5 5 5

输出 #2

31

说明/提示

对于 $30\%$ 的数据：$1\le n\le 20,1\le a_i\le 100$

对于 $60\%$ 的数据：$1\le n\le 100,1\le a_i\le 100$

对于 $100\%$ 的数据：$1\le n\le 100,1\le a_i\le 10^9$