Problem Description

This problem is translated from PA 2020 Round 5 Cukierki.

Bytie is going to Bitek’s birthday party. He knows that Bitek likes sweets, so he wants to give him some candies as a gift. He bought $n$ bags of candies, and the $i$-th bag contains $a_i$ candies.

However, these candies are quite heavy, and Bytie wants to know whether he needs to give all of them to Bitek. He decides that he will choose a non-empty subset of the bags, take them to Bitek, and say: “I have a total of $x$ candies here, how many do you want?”, where $x$ is the total number of candies in the bags brought to the party. After hearing this, Bitek may choose any integer $y$ in the range $[1, x]$. No matter what Bitek answers, Bytie wants to be able to select some of the bags he brought (and keep the rest for himself) so that the total number of candies in the selected bags is exactly $y$. Of course, he cannot tear the wrappers—giving loose candies is impolite.

Therefore, Bytie is thinking: how many different non-empty subsets of bags can he bring so that, regardless of Bitek’s choice, he can give him the desired number of candies? Please help him compute this. Since the number of such subsets may be very large, output it modulo $10^9+7$.

Input Format

The first line contains an integer $n$, the number of candy bags Bytie has.

The second line contains $n$ integers $a_1,a_2,\cdots,a_n$, where $a_i$ is the number of candies in the $i$-th bag.

Output Format

Output the number of possible subsets of candy bags modulo $10^9+7$.

5
2 7 4 4 1

8

Hint

Explanation for Sample 1

Bytie can bring $8$ non-empty subsets: $\{5\}, \{1, 5\}, \{1, 3, 5\}, \{1, 4, 5\}, \{1, 3, 4, 5\}, \{1, 2, 3, 5\}, \{1, 2, 4, 5\}$, and $\{1, 2, 3, 4, 5\}$. For example, if Bytie brings the subset $\{1,2,4,5\}$ and Bitek wants $9$ candies, then Bytie can only give him bags $1$ and $2$. Bytie cannot bring the subset $\{1,2,5\}$, because if Bitek wants $6$ candies then Bytie would not be able to satisfy him.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, it is guaranteed that $1\le n\le 5\times 10^3$ and $1\le a_i\le 5\times 10^3$.

Translated by ChatGPT 5