문제

JOI 군은 초등학교 $1$ 학년이다. JOI 군은 막 배운 덧셈과 뺄셈을 매우 좋아해서, 숫자가 나열되어 있는 것을 보면 마지막 $2$ 개의 숫자 사이에 = 를 넣고 나머지 숫자들 사이에 반드시 + 또는 - 를 넣어 등식을 만들며 논다. 예를 들어 8 3 2 4 8 7 2 4 0 8 8 로부터 등식 8+3-2-4+8-7-2-4-0+8=8 을 만들 수 있다.

JOI 군은 등식을 만든 후, 그것이 올바른 등식인지 계산하여 확인한다. 단, JOI 군은 아직 음수를 모르고 $20$ 을 초과하는 수의 계산은 할 수 없다. 따라서 올바른 등식 중 좌변을 왼쪽부터 계산했을 때 계산 도중에 나타나는 수가 모두 $0$ 이상 $20$ 이하인 등식만이 JOI 군이 확인할 수 있는 올바른 등식이다. 예를 들어, 8+3-2-4-8-7+2+4+0+8=8 은 올바른 등식이지만, 도중에 나타나는 8+3-2-4-8 이 음수이므로 JOI 군은 이 등식이 올바른지 확인할 수 없다.

입력으로 숫자열이 주어졌을 때, JOI 군이 만들고 확인할 수 있는 올바른 등식의 개수를 구하는 프로그램을 작성하시오.

입력

입력 파일은 $2$ 줄로 이루어진다. $1$ 번째 줄에는 나열된 숫자의 개수를 나타내는 정수 $N$ ($3 \le N \le 100$) 이 적혀 있다. $2$ 번째 줄에는 $0$ 이상 $9$ 이하의 정수 $N$ 개가 공백으로 구분되어 적혀 있다.

주어지는 입력 데이터의 $60\%$ 에서는 JOI 군이 만들고 확인할 수 있는 올바른 등식의 개수가 $2^{31}-1$ 을 넘지 않는다. 또한, 주어지는 모든 입력 데이터에서 JOI 군이 만들고 확인할 수 있는 올바른 등식의 개수는 $2^{63}-1$ 을 넘지 않는다.

출력

JOI 군이 만들고 확인할 수 있는 올바른 등식의 개수를 나타내는 정수를 $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

입력 예 $1$ 에서 JOI 군은 $10$ 개의 올바른 등식

• 8+3-2-4+8-7-2-4-0+8=8
• 8+3-2-4+8-7-2-4+0+8=8
• 8+3+2+4-8-7+2-4-0+8=8
• 8+3+2+4-8-7+2-4+0+8=8
• 8+3+2-4+8-7+2+4-0-8=8
• 8+3+2-4+8-7+2+4+0-8=8
• 8-3+2+4-8+7+2+4-0-8=8
• 8-3+2+4-8+7+2+4+0-8=8
• 8-3+2-4+8+7+2-4-0-8=8
• 8-3+2-4+8+7+2-4+0-8=8

을 만들고 확인할 수 있으므로 $10$ 을 출력한다.

입력 예 $2$ 에서 답이 $32$ 비트 부호 있는 정수의 범위에 들어가지 않는다는 점에 주의하시오.

($2015$ 년 $2$ 월 $21$ 일 추가) 사용자의 지적을 통해 입력 예 $1$ 의 설명 중 등식에 오류가 있음이 밝혀졌습니다. 현재는 수정되었습니다. $5$ 번째 등식은 8+3-2-4+8-7+2+4-0-8=8 이었으나 이를 8+3+2-4+8-7+2+4-0-8=8 로 수정했습니다. 또한, $6$ 번째 등식은 8+3-2-4+8-7+2+4+0-8=8 이었으나 이를 8+3+2-4+8-7+2+4+0-8=8 로 수정했습니다.