Постройка забора

시간 제한2초메모리 제한1024 MB

요약

가장 긴 널빤지의 길이가 나머지 길이의 합보다 작은 부분집합의 개수를 세는 문제입니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 조합론, 정렬, 누적 합
정답자: 아직 제출이 없습니다

문제

После побега Колобка Дед и Баба решили построить забор вокруг своего дома, чтобы не допустить повторения истории.

Забор представляет собой многоугольник ненулевой площади, сторонами которого являются доски. Пилить или ломать доски нельзя. Например, из трех досок с длинами $10$ , $11$ и $12$ можно построить забор, а из четырех досок с длинами $100$ , $1$ , $2$ и $3$ --- нельзя.

У Деда нашлось целых $n$ досок, поэтому они с Бабой задались вопросом: а сколько различных способов выбрать несколько досок из имеющихся, чтобы из них затем можно было построить забор? Способы считаются различными, если существует доска, которая используется в одном из них, но не используется в другом.

Пожилым людям надо помогать, так что вам не составит труда решить для них эту задачу! Количество способов может быть довольно большим, поэтому выведите остаток от деления этого количества на число $10^9+7$ .

입력

В первой строке входного файла находится одно натуральное число $n$ ( $1 \le n \le 4000$ ) --- количество досок. Во второй строке дано $n$ чисел $l\_i$ ( $1 \le l\_i \le 4000$ ) --- длины досок.

출력

В выходной файл выведите одно число --- количество способов выбрать доски для постройки забора, взятое по модулю $10^9 + 7$ .

예제3

예제 1
입력
```
3
10 11 12
```
예상 출력
```
1
```
예제 2
입력
```
4
100 1 2 3
```
예상 출력
```
0
```
예제 3
입력
```
4
5 5 5 5
```
예상 출력
```
5
```