Đề bài
JOI-kun là học sinh lớp $1$ tiểu học. JOI-kun rất thích phép cộng và phép trừ vừa mới được học, nên mỗi khi nhìn thấy một dãy các chữ số xếp cạnh nhau, cậu lại chơi trò đặt dấu = vào giữa $2$ chữ số cuối cùng, và luôn đặt dấu + hoặc - vào giữa các chữ số liền kề còn lại để tạo thành một đẳng thức. Ví dụ, từ 8 3 2 4 8 7 2 4 0 8 8, cậu có thể tạo ra đẳng thức 8+3-2-4+8-7-2-4-0+8=8.
Sau khi tạo ra một đẳng thức, JOI-kun tính toán để kiểm tra xem đó có phải là một đẳng thức đúng hay không. Tuy nhiên, JOI-kun vẫn chưa biết số âm và cũng không thể tính toán các số vượt quá $20$. Do đó, trong số các đẳng thức đúng, chỉ những đẳng thức mà khi tính vế trái từ trái sang phải, tất cả các số xuất hiện trong quá trình tính toán đều lớn hơn hoặc bằng $0$ và nhỏ hơn hoặc bằng $20$ mới là những đẳng thức đúng mà JOI-kun có thể kiểm chứng được. Ví dụ, 8+3-2-4-8-7+2+4+0+8=8 là một đẳng thức đúng, nhưng vì 8+3-2-4-8 xuất hiện giữa chừng là một số âm nên JOI-kun không thể kiểm chứng xem đẳng thức này có đúng hay không.
Cho một dãy chữ số làm đầu vào, hãy viết chương trình tìm số lượng đẳng thức đúng mà JOI-kun có thể tạo ra và kiểm chứng được.
Dữ liệu vào
Tệp đầu vào gồm $2$ dòng. Dòng thứ $1$ chứa số nguyên $N$ ($3 \le N \le 100$) biểu thị số lượng chữ số được xếp. Dòng thứ $2$ chứa $N$ số nguyên từ $0$ đến $9$, cách nhau bởi dấu cách.
Trong $60\%$ dữ liệu vào được cho, số lượng đẳng thức đúng mà JOI-kun có thể tạo ra và kiểm chứng không vượt quá $2^{31}-1$. Ngoài ra, trong tất cả dữ liệu vào được cho, số lượng đẳng thức đúng mà JOI-kun có thể tạo ra và kiểm chứng không vượt quá $2^{63}-1$.
Dữ liệu ra
In ra trên $1$ dòng một số nguyên biểu thị số lượng đẳng thức đúng mà JOI-kun có thể tạo ra và kiểm chứng.
Ví dụ
Ví dụ đầu vào 1
11 8 3 2 4 8 7 2 4 0 8 8
Ví dụ đầu ra 1
10
Ví dụ đầu vào 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
Ví dụ đầu ra 2
7069052760
Trong Ví dụ đầu vào $1$, JOI-kun có thể tạo ra và kiểm chứng $10$ đẳng thức đúng sau đây:
8+3-2-4+8-7-2-4-0+8=88+3-2-4+8-7-2-4+0+8=88+3+2+4-8-7+2-4-0+8=88+3+2+4-8-7+2-4+0+8=88+3+2-4+8-7+2+4-0-8=88+3+2-4+8-7+2+4+0-8=88-3+2+4-8+7+2+4-0-8=88-3+2+4-8+7+2+4+0-8=88-3+2-4+8+7+2-4-0-8=88-3+2-4+8+7+2-4+0-8=8
Do đó, in ra $10$.
Trong Ví dụ đầu vào $2$, lưu ý rằng đáp án không nằm trong phạm vi của số nguyên có dấu $32$-bit.
(Bổ sung ngày $21$ tháng $2$ năm $2015$) Theo góp ý từ người dùng, chúng tôi phát hiện có sai sót trong các đẳng thức ở phần giải thích của Ví dụ đầu vào $1$. Hiện tại lỗi này đã được sửa. Đẳng thức thứ $5$ ban đầu là 8+3-2-4+8-7+2+4-0-8=8, đã được sửa thành 8+3+2-4+8-7+2+4-0-8=8. Ngoài ra, đẳng thức thứ $6$ ban đầu là 8+3-2-4+8-7+2+4+0-8=8, đã được sửa thành 8+3+2-4+8-7+2+4+0-8=8.