정부

PO-국의 유권자들이 투표한 결과, $N$개의 정당이 각각 일정한 수의 의석을 얻어 의회에 진출했다. PO-국에서는 모든 정당의 견해가 대체로 비슷하므로(인플레이션 대신 재귀 등), 국회의장은 추첨으로 정부를 정하는 방안을 고려하고 있다. 하지만 그러려면 먼저 가능한 다수 정부가 몇 개인지 알아야 한다.

정부를 구성하는 정당들의 의석수가 나머지 정당들의 의석수보다 많아 의회에서 과반을 차지하도록 정부를 구성하는 방법의 수를 계산하는 프로그램을 작성한다. 정부에는 불필요한 정당이 포함되어서는 안 된다. 즉, 정부에서 어떤 정당 하나를 제외한 뒤에도 여전히 과반을 유지할 수 있다면 그 정부 구성은 세지 않는다.

입력의 첫 번째 줄에 정당의 수 $N$, $2 \le N \le 35$이 주어진다.

그다음 줄에는 $N$개의 수, 즉 각 정당의 의석수(항상 정수)가 주어진다. 각 정당은 적어도 하나의 의석을 가지며, 전체 의석수는 1000을 초과하지 않는다.

위 조건에 따른 가능한 정부 구성의 수를 하나의 수로 출력한다. 정답은 2십억을 초과하지 않는다.