Problem Statement

You are given integers $N$, $K$, and a correct bracket sequence $S$ of length $K$ consisting of ( and ).

Find the number, modulo $998244353$, of length-$N$ strings $T$ consisting of ( and ) that satisfy all of the following conditions:

• There exists a (not necessarily contiguous) subsequence of $T$ that is a correct bracket sequence of length $K$.
• Among all (not necessarily contiguous) subsequences of $T$ that are correct bracket sequences of length $K$, the lexicographically largest one is $S$.

Here, concerning the lexicographical order of strings consisting of ( and ), we consider ( smaller than ).

Notes on correct bracket sequences A correct bracket sequence is a string that can be transformed into the empty string by repeatedly deleting a substring that is () zero or more times.

Notes on lexicographical order A string $S = S_1S_2\ldots S_{|S|}$ is said to be lexicographically smaller than a string $T = T_1T_2\ldots T_{|T|}$ if either of the following holds. $|S| < |T|$ and $S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}$. There exists an integer $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$ such that: $S_1S_2\ldots S_{i-1} = T_1T_2\ldots T_{i-1}$, $S_i$ is a character smaller than $T_i$.

Constraints

• $K \leq N \leq 10^7$
• $2 \leq K \leq 5 \times 10^5$
• $N$ and $K$ are integers.
• $S$ is a correct bracket sequence of length $K$.

Input

The input is given from Standard Input in the following format:

N K
S

Output

Print the answer.