Hôm nay Alice và Bob sẽ chơi một trò chơi về chuỗi ngoặc đúng.

Bob định nghĩa rằng một chuỗi ngoặc đúng khi:

• Chuỗi rỗng là một chuỗi ngoặc đúng.
• Nếu \(A\) là một chuỗi ngoặc đúng thì \((A)\) cũng là một chuỗi ngoặc đúng.
• Nếu \(A\) và \(B\) là một dãy ngoặc đúng thì \(AB\) cũng là một chuỗi ngoặc đúng.

Bob đưa ra một chuỗi \(S\) bao gồm các kí tự (, ), ?. Bob yêu cầu Alice hãy đếm số cách tạo ra chuỗi \(T\) bằng cách thay đổi các kí tự ? thành các kí tự (, ) để \(T\) trở thành một chuỗi ngoặc đúng.

Alice nhận thấy rằng có \(2^x\) cách để tạo ra một chuỗi \(T\) nhưng không biết cách nào để xác định được \(T\) là một chuỗi ngoặc đúng. \((x\) là số lượng kí tự ? trong chuỗi \(S)\).

Hãy giúp Alice giải câu đố của Bob nhé. Vì kết quả có thể rất lớn, hãy in ra giá trị sau khi lấy dư \(998244353\).

Input

• Một dòng duy nhất chứa xâu \(S\) \((1 \le |S| \le 3000)\).

Output

• Số lượng xâu \(T\) là một chuỗi ngoặc đúng.

Sample Input

(???(?

Sample Output

2

Giải thích

• Có \(2\) xâu \(T\) thoả mãn là chuỗi ngoặc đúng: ()()(), (())().

Ràng buộc

• \(50\%\) số test tương ứng với \(1 \le |S| \leq 15.\)
• \(50\%\) số test tiếp theo tương ứng với \(1 \le |S| \le 3000.\)