G. Koxia and Brackettime limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputChiyuu has a bracket sequence^\dagger s of length n. Let k be the minimum number of characters that Chiyuu has to remove from s to make s balanced^\ddagger.Now, Koxia wants you to count the number of ways to remove k characters from s so that s becomes balanced, modulo 998\,244\,353.Note that two ways of removing characters are considered distinct if and only if the set of indices removed is different.^\dagger A bracket sequence is a string containing only the characters "(" and ")".^\ddagger A bracket sequence is called balanced if one can turn it into a valid math expression by adding characters + and 1. For example, sequences (())(), (), (()(())) and the empty string are balanced, while )(, ((), and (()))( are not.InputThe first line of input contains a string s (1 \leq |s| \leq 5 \cdot {10}^5) — the bracket sequence.It is guaranteed that s only contains the characters "(" and ")".OutputOutput a single integer — the number of ways to remove k characters from s so that s becomes balanced, modulo 998\,244\,353.ExamplesInput
())(()
Output
4
Input
(
Output
1
NoteIn the first test case, it can be proved that the minimum number of characters that Chiyuu has to remove is 2. There are 4 ways to remove 2 characters to make s balanced as follows. Deleted characters are noted as red.  \texttt{(} \color{Red}{\texttt{)}} \texttt{)} \color{Red}{\texttt{(}} \texttt{(} \texttt{)},  \texttt{(} \texttt{)} \color{Red}{\texttt{)}} \color{Red}{\texttt{(}} \texttt{(} \texttt{)},  \texttt{(} \color{Red}{\texttt{)}} \texttt{)} \texttt{(} \color{Red}{\texttt{(}} \texttt{)},  \texttt{(} \texttt{)} \color{Red}{\texttt{)}} \texttt{(} \color{Red}{\texttt{(}} \texttt{)}. In the second test case, the only way to make s balanced is by deleting the only character to get an empty bracket sequence, which is considered balanced.
())(()

4 
['divide and conquer', 'fft', 'math', '*3400']