Biểu thức ngoặc là xâu chỉ gồm các ký tự ‘(’ hoặc ‘)’. Biểu thức ngoặc đúng được định nghĩa một cách đệ qui như sau:

- Biểu thức rỗng là biểu thức ngoặc đúng,
- Nếu A là biểu thức ngoặc đúng thì (A) cũng là một biểu thức ngoặc đúng,
- Nếu A và B là hai biểu thức ngoặc đúng thì AB cũng là một biểu thức ngoặc đúng.

Ví dụ, ‘()(())’ là một biểu thức ngoặc đúng.

Yêu cầu: Cho S là một xâu chỉ gồm các ký tự ‘(‘, ‘)’ và ‘?’, hãy đếm số cách cách thay các ký tự ‘?’ trong xâu S thành ký tự ‘(‘ hoặc ‘)’ để nhận được xâu T là biểu thức ngoặc đúng.

Input

Một dòng chứa xâu S (độ dài xâu S không vượt quá 200) chỉ gồm các ký tự ‘(‘, ‘)’ và ‘?’.

Output

Một dòng là số cách thay ký tự ‘?’ trong xâu S thành ký tự ‘(‘ hoặc ‘)’ để nhận được xâu T là biểu thức ngoặc đúng.