Problem Statement

A string $t$ consisting only of (,),? is called a good string if it satisfies the following condition.

• By appropriately replacing each ? in $t$ with either (,), $t$ can be made into a correct bracket sequence.

For example, $t=$ ?(?) is a good string, since it can be made into (()) by replacing the ? characters.
Similarly, $t=$ ???? and $t=$ ()()() are also good strings ($t$ does not necessarily have to contain ?).
On the other hand, $t=$ )??? is not a good string, since it does not become a correct bracket sequence no matter how the ? characters are replaced.

You are given a string $s$ consisting only of (,),?,..
How many good strings can be obtained by replacing each . in $s$ with one of (,),??
Since the answer can be very large, find it modulo $998244353$.

Notes

1. The empty string is a correct bracket sequence.
2. If a string $A$ is a correct bracket sequence, then the string formed by concatenating ($,A,$ ) in this order is also a correct bracket sequence.
3. If non-empty strings $A,B$ are correct bracket sequences, then the string formed by concatenating $A,B$ in this order is also a correct bracket sequence.
4. Only strings satisfying one of the conditions 1 to 3 above are correct bracket sequences.

Constraints

• $s$ is a string consisting only of (,),?,..
• $1\le |s|\le 4000$

Input

The input is given from standard input in the following format.

$s$

Output

Output the number of good strings that can be obtained by replacing each . in $s$ with one of (,),?, modulo $998244353$.

Sample

..

4

((.?

2

(())

1

((()

0

(...)?..?.

358