초등학교 1학년 (초딩) timer 1000초 memory 64MB

초인이가 초등학교 1학년때 이야기이다. 초인이는 막 배운 덧셈, 뺄셈을 아주 좋아해서, 

숫자가 줄 지어있는 것을 보면 마지막 두 숫자 사이에 "="를 넣고 나머지 숫자 사이에 "+"또는 "- "을 넣어 등식을 만들어 놀곤 했다. 예를 들어 "8 3 2 4 8 7 2 4 0 8 8"라는 수열을 보면 등식 "8 + 3-2-4 + 8-7-2-4-0 + 8 = 8"을 만들고 아주 재미있어 했다.

초인이는 등식을 만든 후, 그것이 올바른 등식인지를 확인하고자 한다. 

그러나 초인이는 아직 1학년이므로 음수는 모르고 계산의 중간 결과가 20을 초과하는 계산은 할 수 없다.

따라서 만들어진 등식 중 왼쪽에서부터 계산했을 때 계산의 중간에 나타나는 숫자가 

모두 0 이상 20 이하의 등식 만 초인이가 확인할 수 있는 올바른 등식이다. 

예를 들어, "8 + 3-2-4-8-7 + 2 + 4 + 0 + 8 = 8"는 적절한 등식이지만,

중간에 나타나는 8 + 3-2-4-8이 음수이므로 초인이는 등식이 정확한지 확인할 수 없어 초인이 입장에서는 올바른 등식이 아니다.

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

입력 예 1의 경우를 살펴보면 아래와 같이 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