Probability of Generating a Parentheses Sequence

Mivik has devised an algorithm to randomly generate a valid parentheses sequence of length 2n. The algorithm works as follows:

function generate(n):
    let len = 2 * n
    // Create an array of length len with n zeros and n ones
    // Here 0 represents '(' and 1 represents ')'
    arr = [0]*n + [1]*n
    shuffle(arr)  // uniformly random permutation
    i = 0, sum = 0
    while i < len:
        sum += (arr[i] == 0 ? 1 : -1)
        if sum < 0:
            // i is the first index causing an illegal prefix
            // Find j > i such that after adding, sum becomes 0
            j = i + 1
            while j < len:
                sum += (arr[j] == 0 ? 1 : -1)
                if sum == 0:
                    break
                j++
            // Flip the entire segment [i, j]
            for k from i to j:
                arr[k] = arr[k] xor 1
            i = j + 1
        else:
            i++
    // Convert zeros to '(' and ones to ')'
    return string formed by arr

This algorithm always produces a valid parentheses sequence but the resulting distribution is not uniform. In particular, when n = 3 the sequence ()()() is produced with a much higher probability than ((())).

More formally, for a fixed n, consider that the algorithm starts with a uniformly random shuffle among all arrays that contain exactly n zeros and n ones (a total of \(\binom{2n}{n}\) possibilities). Then it fixes any illegal prefixes by flipping certain contiguous subarrays. For a final valid parentheses sequence \(s\), let its prefix sums (with \('(' = +1\) and \(')' = -1\)) be defined as \(p_0 = 0, p_i = \sum_{j=1}^{i} a_j\) for \(1 \le i \le 2n\) where \(a_j = 1\) if \(s_j = '('\) and \(a_j = -1\) if \(s_j = ')'\). Observe that \(p_{2n} = 0\) and \(p_i \ge 0\) for all \(i\) since \(s\) is valid. Define r as the number of indices \(i\) with \(1 \le i \le 2n-1\) such that \(p_i = 0\) (i.e. the number of times, excluding the beginning and end, that the running sum returns to zero). It turns out that the number of different initial arrays that lead to \(s\) via the described algorithm is

[ f(s) = 2^{r+1}. ]

Thus, the probability of generating \(s\) is

[ P(s) = \frac{2^{r+1}}{\binom{2n}{n}} \pmod{998244353}. ]

Your task is: given an integer n and a valid parentheses sequence s of length 2n, compute \(P(s)\) modulo \(998244353\). If you are not familiar with computing with rational numbers modulo a prime, you can refer to this link for guidance.

inputFormat

The input consists of two lines. The first line contains a single integer n (1 ≤ n ≤ 10⁵). The second line contains a valid parentheses sequence s of length 2n.

You can assume that s is a valid parentheses sequence.

outputFormat

Output a single integer, the probability that the given valid parentheses sequence is generated by the algorithm, modulo 998244353.

sample

1
()

1