Subset Fight

We are given an array on $n$ integers, where $v_i$ is the number of numbers equal with $i$. A scenario where the humanity is victorious is a scenario where the sum of the numbers from the subset is multiple of $n$.

For example, if $n = 3$ and the numbers from the array are $1$, $2$ and $3$, the array is $\{1, 2, 2, 3, 3, 3\}$.

Even though a number shows up multiple times in the resulting array, the subsets formed by those numbers are different.

With other words, we can count the elements from the array with $1$, $2$, ..., $v_1 + v_2 + ... + v_n$, and we have to find how many subsets among the $2^{v_1 + v_2 + ... + v_n}$ have the sum a multiple of $n$.

Since the number of subsets can be quite large, we need to print its number modulo $10^9 + 7$.

Input

On the first line we have one integer, $n$ ($1 \leq n \leq 100$). On the next line we have the $n$ integers ($1 \leq v_i \leq 2 * 10^5$).

For tests worth 20 points, $\sum_{i=1}^{n} v_i \leq 20$.
For other tests worth 40 points, $\sum_{i=1}^{n} v_i \leq 10^5$.

Output

On the first line the required answer should be printed.

Example 1

stdin

3
1 1 1

stdout

4

Explanation

The correct subsets are $\{ \}$, $\{1, 2\}$, $\{3\}$ and $\{1, 2, 3\}$.

Example 2

stdin

5
69 420 1017 128 953

stdout

985611225