题目描述

小杨有 $n$ 个整数 $a_1, a_2, \ldots, a_n$。

他想从这 $n$ 个整数中选出若干个（至少 $1$ 个）组成一个小组，使得这个小组里所有整数的平均值恰好是一个整数。

请你帮小杨计算：一共有多少种不同的选法？由于答案可能很大，请输出答案对 $10^9 + 7$ 取模的结果。

两种选法不同，当且仅当存在某个整数在一种选法中被选中、在另一种选法中没被选中。

输入格式

输入共两行。

第一行为一个整数 $n$，表示整数的个数。

第二行为 $n$ 个整数 $a_1, a_2, \ldots, a_n$。

输出格式

输出一个整数，表示选法数对 $10^9 + 7$ 取模的结果。

样例

3
2 6 2

6

5
5 5 5 5 5

31

样例解释

样例 1 中，设三个数的位置分别为 $1,2,3$，其中第 $1$ 个和第 $3$ 个数都是 $2$。$6$ 种选法分别为：选位置 $1$、选位置 $2$、选位置 $3$、选位置 $1,2$、选位置 $1,3$、选位置 $2,3$，它们的平均值分别为 $2, 6, 2, 4, 2, 4$，都是整数；而选位置 $1,2,3$ 的平均值为 $\frac{10}{3}$，不是整数。共 $6$ 种。

样例 2 中，任意选法的平均值都是 $5$，一定是整数，$5$ 个数的所有非空子集共 $2^5 - 1 = 31$ 种。

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \leq n \leq 100$，$1 \leq a_i \leq 10^9$。