조각 케이크 (Hard)

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

요약

각 조각의 크기가 1/c_i인 케이크 조각들에서 합이 전체 케이크의 0.99배 이상 1.01배 이하가 되는 부분집합의 개수를 10^9+7로 나눈 나머지로 구합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 조합론, 수학
정답자: 아직 제출이 없습니다

문제

안즈는 생일선물로 조각 케이크를 잔뜩 받았다.

케이크를 먹고 행복해하던 안즈는 남은 케이크를 정리해 냉장고에 넣어야 한다는 귀찮은 일을 깨닫고 말았다.

결국 안즈는 케이크를 정리하는 좋은 방법을 알아냈다. 남은 조각 케이크들을 모아 케이크 한 판으로 만들어 버리는 것이다! 고른 조각 케이크들의 크기의 합이 $\frac{99}{100}$ 판 이상 $\frac{101}{100}$ 판 이하라면 모아서 케이크 한 판으로 만들 수 있다.

입력

첫째 줄에 남은 조각 케이크의 개수 $N$ 이 주어진다.

둘째 줄에는 각 조각 케이크의 크기를 나타내는 정수 $c_i$ 가 공백으로 구분되어 주어진다. $c_i$ 는 $i$ 번째 조각 케이크의 크기가 $\frac{1}{c_i}$ 판임을 뜻한다.

출력

조각 케이크들을 골랐을 때, 고른 조각 케이크를 모두 합쳐서 케이크 한 판으로 만들 수 있는 경우의 수를 출력한다.

답이 매우 커질 수 있으므로, $10^9+7$ 로 나눈 나머지를 출력한다.

제한

$1 \le N \le 105$
$2 \le c_i \le 25$

예제2

예제 1
입력
```
6
3 4 6 7 9 10
```
예상 출력
```
2
```
예제 2
입력
```
10
2 2 4 4 4 4 8 8 8 8
```
예상 출력
```
94
```