1학년

상근이는 덧셈과 뺄셈을 좋아합니다. 숫자가 한 줄로 나열되어 있으면, 마지막 두 숫자 사이에는 =을, 나머지 인접한 숫자 사이에는 + 또는 -를 넣어 하나의 등식을 만듭니다. 예를 들어 숫자열 8 3 2 4 8 7 2 4 0 8 8로는 8+3-2-4+8-7-2-4-0+8=8과 같은 등식을 만들 수 있습니다.

상근이는 올바른 등식만 만들려고 합니다. 상근이는 아직 음수를 배우지 않았고 20보다 큰 수도 다루지 못합니다. 따라서 등식의 왼쪽 부분을 맨 앞에서부터 차례대로 계산할 때, 계산 도중에 나타나는 모든 중간 값이 항상 $0$ 이상 $20$ 이하이어야 합니다. 예를 들어 8+3+2-4-8-7+2+4+0+8=8은 수식 자체로는 성립하지만, 왼쪽부터 계산하면 8+3+2-4-8-7에서 값이 음수가 되므로 상근이가 만들 수 없는 등식입니다.

숫자열이 주어졌을 때, 상근이가 만들 수 있는 올바른 등식의 개수를 구하는 프로그램을 작성하세요.

첫째 줄에 숫자의 개수 $N$이 주어집니다. ($3 \le N \le 100$) 둘째 줄에는 $0$ 이상 $9$ 이하의 정수 $N$개가 공백으로 구분되어 주어집니다.

상근이가 만들 수 있는 올바른 등식의 개수를 첫째 줄에 출력합니다. 이 값은 항상 $2^{63}-1$ 이하입니다.

숫자열 8 3 2 4 8 7 2 4 0 8 8의 경우, 다음과 같이 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