Đề bài

Helena vừa hoàn thành năm đầu tiên ở trường tiểu học. Cô bé là một học sinh gương mẫu, luôn đạt điểm cao và đặc biệt yêu thích toán học. Hiện Helena đang tận hưởng kỳ nghỉ xứng đáng cùng gia đình, nhưng cô bắt đầu nhớ những bài tập toán hằng ngày. May thay, anh trai của Helena quyết định thỏa mãn niềm đam mê ấy bằng bài toán sau.

Một biểu thức hợp lệ được định nghĩa đệ quy như sau:

• Xâu ? là một biểu thức hợp lệ, biểu diễn một số.
• Nếu \(A\) và \(B\) là các biểu thức hợp lệ thì min(A,B) và max(A,B) cũng là các biểu thức hợp lệ. Biểu thức thứ nhất trả về số nhỏ hơn trong hai đối số, còn biểu thức thứ hai trả về số lớn hơn.

Ví dụ, min(min(?,?),min(?,?)) và max(?,max(?,min(?,?))) là các biểu thức hợp lệ, còn ??, max(min(?)) và min(?,?,?) thì không.

Helena nhận được một biểu thức hợp lệ chứa tổng cộng \(N\) dấu hỏi. Mỗi dấu hỏi phải được thay bằng một số thuộc tập \(\{1,2,\ldots,N\}\) sao cho mỗi số trong tập xuất hiện đúng một lần trong biểu thức. Nói cách khác, các dấu hỏi được thay bằng một hoán vị của các số từ \(1\) đến \(N\).

Sau khi thay các dấu hỏi bằng số, ta có thể tính giá trị biểu thức; kết quả là một số nguyên từ \(1\) đến \(N\). Xét mọi cách gán số cho các dấu hỏi, Helena có thể thu được bao nhiêu giá trị khác nhau?

Dữ liệu vào

Dòng duy nhất chứa một biểu thức hợp lệ.

Dữ liệu ra

In một số nguyên từ \(1\) đến \(N\): số lượng giá trị khác nhau có thể thu được khi tính biểu thức.

Ràng buộc

Trong tất cả các subtask, \(2\le N\le 1\,000\,000\).

Phân nhóm

• Subtask 1 (10 điểm): \(N\le 9\).
• Subtask 2 (13 điểm): \(N\le 16\).
• Subtask 3 (13 điểm): Mỗi hàm trong biểu thức có ít nhất một đối số là dấu hỏi ?.
• Subtask 4 (30 điểm): \(N\le 1\,000\).
• Subtask 5 (34 điểm): Không có ràng buộc bổ sung.

Ví dụ

min(min(?,?),min(?,?))

1

max(?,max(?,min(?,?)))

2

min(max(?,?),min(?,max(?,?)))

3