After Kolobok escaped, Grandfather and Baba decided to build a fence around their house to prevent history from repeating itself.
The fence is a polygon of non-zero area, the sides of which are boards. Do not cut or break boards. For example, from three boards with lengths 10, 11 and 12 you can build a fence, and from four boards with lengths 100, 1, 2 and 3 — can't.
Grandfather found as many as n boards, so he and Baba asked themselves the question: how many different ways to choose several boards from the available ones so that they can then be used to build a fence? Ways are considered different if there is a board that is used in one of them but not used in the other.
Elderly people need help, so it will not be difficult for you to solve this problem for them! The number of ways can be quite large, so print the remainder after dividing this number by 10
9 + 7.
Input file format
The first line of the input file contains one natural number n (1 ≤ n ≤ 4000) — number of boards. The second line contains n numbers li (1 ≤ l
i ≤ 4000) — board lengths.
Output file format
In the output file print a single number — the number of ways to choose boards for building a fence, modulo 10
9 + 7.
|
Enter |
Output |
3
10 11 12
|
1 |
4
100 1 2 3
|
0 |
4
5 5 5 5
|
5 |