JOI là học sinh lớp một. Cậu rất thích phép cộng và phép trừ vừa được học. Mỗi khi nhìn thấy một dãy chữ số, cậu lại chơi trò tạo đẳng thức bằng cách đặt dấu = giữa hai chữ số cuối cùng, rồi đặt đúng một dấu + hoặc - vào mỗi khoảng trống còn lại giữa các chữ số. Chẳng hạn, từ dãy 8 3 2 4 8 7 2 4 0 8 8, cậu có thể tạo đẳng thức

Sau khi tạo một đẳng thức, JOI tính toán để kiểm tra xem đẳng thức đó có đúng hay không. Tuy nhiên, cậu chưa biết số âm và chưa thể tính toán với các số lớn hơn \(20\). Vì vậy, trong số những đẳng thức đúng, cậu chỉ có thể kiểm tra những đẳng thức mà khi tính vế trái từ trái sang phải, mọi giá trị xuất hiện trong quá trình tính đều nằm trong khoảng từ \(0\) đến \(20\), kể cả hai đầu mút.

Chẳng hạn, đẳng thức

là đúng, nhưng biểu thức trung gian \(8+3-2-4-8\) có giá trị âm nên JOI không thể kiểm tra đẳng thức này.

Yêu cầu

Cho một dãy chữ số, hãy viết chương trình đếm số đẳng thức đúng mà JOI có thể tạo ra và kiểm tra được.

Dữ liệu vào

Dữ liệu gồm \(2\) dòng:

• Dòng \(1\) chứa số nguyên \(N\), là số chữ số trong dãy.
• Dòng \(2\) chứa \(N\) số nguyên từ \(0\) đến \(9\), cách nhau bởi dấu cách.

Dữ liệu ra

In ra một dòng chứa một số nguyên là số đẳng thức đúng mà JOI có thể tạo ra và kiểm tra được.

Ràng buộc

• \(3 \le N \le 100\).
• Mỗi số trong dãy là số nguyên từ \(0\) đến \(9\).
• Với mọi dữ liệu đầu vào, số đẳng thức đúng mà JOI có thể tạo ra và kiểm tra được không vượt quá \(2^{63}-1\).

Phân nhóm

• Trong \(60\%\) dữ liệu đầu vào, số đẳng thức đúng mà JOI có thể tạo ra và kiểm tra được không vượt quá \(2^{31}-1\).

Ví dụ

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

10

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

7069052760