일렬로 놓인 숫자들을 이용하여 등식을 만들려고 한다.

마지막 두 숫자 사이에는 등호 =를 넣고, 그보다 앞에 있는 숫자들의 사이에는 덧셈 기호 + 또는 뺄셈 기호 - 중 하나를 넣는다. 계산은 일반적인 연산자 우선순위를 적용하지 않고 왼쪽부터 차례대로 수행한다.

아직 음수와 \(20\)보다 큰 수를 다룰 수 없으므로, 왼쪽부터 계산하는 동안 나타나는 모든 중간 결과가 \(0\) 이상 \(20\) 이하여야 한다. 또한 최종 계산 결과는 등호 오른쪽의 마지막 숫자와 같아야 한다.

주어진 숫자들로 만들 수 있는 올바른 등식의 개수를 구하여라.

입력

첫째 줄에 숫자의 개수 \(N\)이 주어진다.

둘째 줄에 \(0\) 이상 \(9\) 이하의 정수 \(N\)개가 공백으로 구분되어 주어진다.

• \(3 \le N \le 100\)

출력

첫째 줄에 만들 수 있는 올바른 등식의 개수를 출력한다.

답은 \(2^{63}-1\) 이하이다.

예제 입력 1

11
8 3 2 4 8 7 2 4 0 8 8

예제 출력 1

10

예제 입력 2

40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1

예제 출력 2

7069052760