시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 80 12 10 47.619%

문제

평화로운 린카루 마을에는 $N$개의 일거리가 있고, 이를 린카루, 아드, 그리고 래리에게 분배하려고 한다.

아드와 래리는 공평함을 중시하기 때문에, 두 명이 일로 받는 보수의 합이 $D$ 차이를 넘어서는 안된다.

모든 일이 린카루, 아드 또는 래리 중 한 명에게만 돌아간다고 할 때, 일을 나누는 가짓수를 구하여라.

일을 맡은 두 사람이 다른 일이 존재한다면, 일을 나누는 두 방법은 다르다.

입력

첫째 줄에는, 일의 갯수 $N$이 들어 온다. 둘째 줄에는, 보수를 의미하는 $N$개의 정수 $A_1$, $\cdots$, $A_N$개가 공백을 사이에 두고 구분되어 들어온다. 셋째 줄에는, 넘으면 안되는 보수의 합의 차이인 $D$가 들어온다. ($1 \le N \le 30$, $1 \le A_i \le 10^{16}$, $1 \le D \le 10^{18}$)

출력

일을 나누는 서로 다른 방법의 수를 출력하여라.

예제 입력

3
1 2 3
1

예제 출력

9

예제 입력 2

3
1 2 3
0

예제 출력 2

3

힌트