Bajtek is going to Bitek's birthday party. He knows that Bitek loves sweets, so he would like to give him a certain number of candy packages as a gift. He bought $n$ packages, where the $i$-th package contains $a_i$ candies.

The packages are quite heavy, and Bajtek wonders if he must take all of them to Bitek. He decided that he will choose a non-empty subset of packages, take them to Bitek, and say, "I have a total of $x$ candies here, how many of them would you like?", where $x$ is the total number of candies in the packages brought to the party. Upon hearing this, Bitek will likely choose any integer $y$ in the range $[1, x]$. Bajtek would like to be able, regardless of Bitek's choice, to select a part of the brought packages (and keep the rest for himself) such that the total number of candies in those packages is exactly $y$. Of course, there is no question of tearing open the packages – giving candies without the packaging would be impolite.

Bajtek wonders how many non-empty subsets of packages he can take to Bitek so that he is able, regardless of the birthday boy's choice, to present him with the requested number of candies. Help him and calculate this! Since the number of such subsets can be very large, it is sufficient to provide the remainder when divided by $10^9 + 7$.

Input

The first line of the input contains a single integer $n$ ($1 \le n \le 5000$) representing the number of candy packages Bajtek has.

The second line contains a sequence of $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 5000$) representing the number of candies in each of Bajtek's packages.

Output

The output should contain a single integer representing the number of possible subsets of packages that Bajtek can take to Bitek, modulo $10^9 + 7$.

Examples

Input 1

5
2 7 4 4 1

Output 1

8

Note

Explanation of the example: Bajtek can take 8 different subsets of packages to Bitek: $\{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\}$. If he decides, for example, to take the first, second, fourth, and fifth packages, and Bitek asks for 9 candies, he can only give him the first and second packages. Bajtek cannot decide, for example, to take only the first, second, and fifth packages, because Bitek could ask for, say, 6 candies, which would leave Bajtek helpless.