Người ta muốn viết lại biểu thức trên bằng cách thêm các dấu ngoặc vào biểu thức có dạng: sao cho biểu thức có giá trị không đổi và biểu thức sau khi thêm là biểu thức ngoặc đầy đủ, tức là không có biểu thức dạng: và mỗi dấu ngoặc chỉ trong trực tiếp một dấu ngoặc.
Chẳng hạn:
Bạn được cho trước biểu thức chỉ gồm các phép toán , bạn hãy tính số cách thêm các dấu ngoặc thỏa mãn các yêu cầu trên. Vì số này có thể rất lớn nên bạn chỉ cần lấy phần dư cho .
Dữ liệu vào:
Dòng đầu ghi số là số phép toán cộng trừ trong biểu thức ;
Mỗi dòng trong dòng tiếp theo, mỗi dòng ghi một phép toán .
Dữ liệu ra:
Ghi một số duy nhất là số cách thêm ngoặc thỏa mãn các yêu cầu (mod ).
