홍준이와 반물질

면접 대비

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

요약

길이 2 이상인 연속 부분 배열 중 원소들을 합이 같은 두 부분으로 나눌 수 있는 경우의 수를 1e9+7로 나눈 나머지를 구한다.

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

문제

홍준이에게 물질 N개가 일렬로 놓여 있다. 각 물질의 양은 자연수다.

홍준이는 연속한 물질 구간을 하나 고른 뒤, 고른 물질 중 일부를 반물질로 바꾸어 마법을 부린다. 마법이 성공하려면 물질로 남은 것의 양의 합과 반물질로 바꾼 것의 양의 합이 같아야 한다. 물질을 하나도 고르지 않으면 마법을 부릴 수 없으므로 연속한 물질을 2개 이상 골라야 한다.

고른 구간이 다르거나 반물질로 바꾼 물질의 집합이 다르면 서로 다른 경우로 센다. 물질의 양이 주어질 때 마법이 성공하는 경우의 수를 구하라.

입력

첫째 줄에 물질의 개수 N ( $1 \le N \le 1000$ )이 주어진다.

둘째 줄에 i번째 물질의 양 $a_i$ ( $1 \le a_i \le 10000$ )가 공백으로 구분되어 주어진다.

모든 물질의 양의 합은 10000을 넘지 않는다.

출력

마법이 성공하는 경우의 수를 $10^9+7$ 로 나눈 나머지를 출력한다.

예제6

예제 1
입력
```
4
1 1 1 1
```
예상 출력
```
12
```
예제 2
입력
```
1
5
```
예상 출력
```
0
```
예제 3
입력
```
2
3 3
```
예상 출력
```
2
```
예제 4
입력
```
2
1 2
```
예상 출력
```
0
```
예제 5
입력
```
3
1 4 5
```
예상 출력
```
2
```
예제 6
입력
```
5
1 2 3 4 5
```
예상 출력
```
6
```