Giải bài trực tuyến

Cho dãy các phép tính số học chỉ gồm các phép cộng trừ các số nguyên không âm. Ví dụ :

• 1 – 2 + 3 – 4 – 5

Bạn được phép đặt các dấu ngoặc ‘(‘, ‘)’ vào dãy phép tính mà ko được thay đổi các dấu cộng trừ. Với mỗi cách đặt bạn sẽ được các kết quả khác nhau. Ví dụ :

• 1 - 2 + 3 - 4 - 5 = -7
• 1 - (2 + 3 - 4 - 5) = 5
• 1 - (2 + 3) - 4 - 5 = -13
• 1 - 2 + 3 - (4 - 5) = 3
• 1 - (2 + 3 - 4) - 5 = -5
• 1 - (2 + 3) - (4 - 5) = -3

Câu hỏi đặt ra cho bạn là có bao nhiêu giá trị khác nhau có thể nhận được bằng cách đặt các dấu ngoặc vào dãy phép tính như trên?

Input

Mỗi test gồm 5 test nhỏ, mỗi test nhỏ là 1 dãy phép tính gồm N số nguyên ko âm (N <= 30) được ghi trên 1 dòng, các số được nối bởi dấu cộng hoặc trừ. Không có dấu trừ ở đầu dãy và không có dấu cách. Các số trong test <= 100.

Output

Với mỗi bộ test ghi ra số lượng giá trị khác nhau nhận được bằng cách thêm dấu ngoặc vào dãy phép tính. Kết quả mỗi bộ test in trên 1 dòng.

Chú ý

Có 50% số test N <= 10

Example

Input:
1-2+3-4-5
38+29-91
54-18+22+74

Output:
6
1
3