Background

Eientei is a mysterious house hidden in the Lost Forest.

To avoid the arrival of the Lunar emissaries, and also for defense, an endless corridor was set up inside Eientei. Opponents trapped within cannot reach reality, and fall into the trap of eternity and the instant.

However, the endless corridor $S$ is, after all, just an infinite repetition of a single finite corridor $S_0$. Its essence is a trap set by Eientei’s owners, Houraisan Kaguya and Yagokoro Eirin. Because this corridor is realized through Kaguya’s power, Kaguya can affect the “infinitely long” corridor $S$ by modifying the “finite-length” corridor $S_0$. This means that finite modifications can create infinite changes.

A bare corridor looks monotonous and is also hard to use for concealment. Kaguya decided to paint “upper crescent moons” (symbolizing the beginning of the month) and “lower crescent moons” (symbolizing the end of the month) on the corridor, so that the patterns interleave and overlap. For convenience, an “upper crescent moon” can be approximately regarded as a left parenthesis, and a “lower crescent moon” can be approximately regarded as a right parenthesis. As the elegant princess of the Lunar Capital, there are of course many rules—now it is your turn to help Kaguya satisfy her requirements.

Background

Eientei is a mysterious house hidden in the Lost Forest.

To avoid the arrival of the Lunar emissaries, and also for defense, an endless corridor was set up inside Eientei. Opponents trapped within cannot reach reality, and fall into the trap of eternity and the instant.

However, the endless corridor $S$ is, after all, just an infinite repetition of a single finite corridor $S_0$. Its essence is a trap set by Eientei’s owners, Houraisan Kaguya and Yagokoro Eirin. Because this corridor is realized through Kaguya’s power, Kaguya can affect the “infinitely long” corridor $S$ by modifying the “finite-length” corridor $S_0$. This means that finite modifications can create infinite changes.

A bare corridor looks monotonous and is also hard to use for concealment. Kaguya decided to paint “upper crescent moons” (symbolizing the beginning of the month) and “lower crescent moons” (symbolizing the end of the month) on the corridor, so that the patterns interleave and overlap. For convenience, an “upper crescent moon” can be approximately regarded as a left parenthesis, and a “lower crescent moon” can be approximately regarded as a right parenthesis. As the elegant princess of the Lunar Capital, there are of course many rules—now it is your turn to help Kaguya satisfy her requirements.

Problem Description

Kaguya wants to create an infinite parenthesis sequence $S$ as the painting pattern of Eientei’s corridor. It is formed by repeating a parenthesis sequence $S_0$ of length $n$ over and over again.

We say a parenthesis sequence $T$ is valid if and only if it can be generated in the following way:

• $\verb!()!$ is a valid parenthesis sequence.
• If $A$ is a valid parenthesis sequence, then $\verb!(!A\verb!)!$ is also a valid parenthesis sequence.
• If both $A$ and $B$ are valid parenthesis sequences, then $AB$ (i.e. concatenating $A$ and $B$) is also a valid parenthesis sequence.

For example, $\verb!(()())!,\verb!()()!,\verb!((()())())!$ are all valid parenthesis sequences; while $\verb!)(!,\verb!(()!,\verb!())(()!$ are not.

Now Kaguya has already fixed some of the symbols in $S_0$. You need to compute the number of ways to “draw parentheses in the remaining cells such that an infinitely long valid parenthesis sequence can be found in this infinite corridor”. Two ways are considered different if there exists at least one position where ? is replaced by a different character. Output the result modulo $998,244,353$ (a large prime).

Input Format

• The first line contains a positive integer $n$, the total number of cells.
• The next line contains $n$ characters. If the $i$-th character is $\verb!(!$ or $\verb!)!$, it means the parenthesis drawn in the $i$-th cell has been fixed by Kaguya; if the $i$-th character is $\verb!?!$, it means this position is not yet determined.

Output Format

• One line with one integer, the number of all valid ways modulo $998,244,353$.

4
(???

3

8
(???))??

10

Hint

Explanation for Sample 1

There are three valid ways in total: $\verb!(())!$, $\verb!()()!$, and $\verb!())(!$.

• For the first way, $\overbrace{\text{\tt\textcolor{red}{(())}\textcolor{blue}{(())}\texttt{...}\textcolor{red}{(())}\textcolor{blue}{(())}}}^{\text{无穷个}}$ contains an infinitely long valid parenthesis sequence.
• For the second way, $\overbrace{\text{\tt\textcolor{red}{()()}\textcolor{blue}{()()}\texttt{...}\textcolor{red}{()()}\textcolor{blue}{()()}}}^{\text{无穷个}}$ also contains an infinitely long valid parenthesis sequence.
• For the third way, $\text{\tt\textcolor{red}{())}}\overbrace{\text{\tt\textcolor{red}{(}\textcolor{blue}{())(}\texttt{...}\textcolor{red}{())(}\textcolor{blue}{())}}}^{\text{无穷个}}\text{\tt\textcolor{blue}{(}} still contains an infinitely long parenthesis sequence.

It can be proven that no other ways exist.

Constraints and Notes

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n\le } & \textbf{Special Property} & \textbf{Score} \cr\hline 1 & 20 & - & 20 \cr\hline 2 & 10^5 & \text{A} & 10 \cr\hline 3 & 10^5 & \text{B} & 10 \cr\hline 4 & 10^5 & - & 60 \cr\hline \end{array}$$

Special Property $\textbf{A}$: The string contains only $\verb!(!$ and $\verb!)!$.
Special Property $\textbf{B}$: The string contains only $\verb!?!$.

For all testdata, $1\le n\le 10^5$, and the string contains only $\verb!(!,\verb!)!,\verb!?!$ three kinds of characters.

Translated by ChatGPT 5