Infinite Valid Parentheses Sequence

In this problem, you are given an integer n and a bracket sequence S₀ of length n consisting of characters '(' , ')' and '?' (a placeholder). The infinite sequence S is created by repeating S₀ indefinitely. A bracket sequence T is defined as legal if and only if it can be generated by the following rules:

• () is a legal sequence.
• If A is legal then (A) is legal.
• If A and B are legal then their concatenation AB is legal.

For example, (()()), ()() and ((()())()) are legal bracket sequences, while )(, (() and ())(() are not.

You are also given that some characters in S₀ are already fixed as either '(' or ')'. Your task is to replace every '?' with either '(' or ')' in such a way that the infinite sequence S (which is S₀ repeated infinitely) contains an infinite-length legal bracket sequence. Two replacement schemes are considered different if there is at least one position where the replacement differs. Since the answer can be very large, output it modulo \(998\,244\,353\).

Note: Although the definition of legal bracket sequences is for finite strings, an infinite legal bracket sequence in this problem is understood as follows: There exists some starting position in the infinite sequence S such that, if you read from that position onward, the contiguous block of length m\(\cdot n\) (for every positive integer m) is a legal bracket sequence. One can show that this is equivalent to the condition that the period S₀ (after replacement) is balanced (i.e. it contains exactly n/2 '(' and n/2 ')'). This is because any balanced bracket sequence has a unique cyclic shift which forms a legal bracket sequence (this is an immediate consequence of the cyclic lemma).

In summary, you only need to count the number of ways to replace all '?' so that the resulting sequence S₀ is balanced. Let cntOpen be the number of fixed '('; cntClose be the number of fixed ')'; and let q be the number of '?' characters. For the final sequence to be balanced, the number of '(' must be n/2. Thus, if we define x = n/2 - cntOpen, then you have to choose exactly x positions out of the q placeholders to be '(' (and fill the rest with ')'). If x is negative or greater than q, the answer is 0.

inputFormat

The input consists of two lines:

1. The first line contains an integer n (1 \leq n \leq 10^6), the length of the bracket sequence S₀.
2. The second line contains a string of length n consisting of characters '(', ')' and '?'.

It is guaranteed that n is a positive integer. Note that n may be odd; in that case, it is impossible to obtain a balanced sequence, and the answer is 0.

outputFormat

Output a single integer—the number of ways to replace all '?' such that the infinite sequence S contains an infinite legal bracket sequence, modulo 998,244,353.

sample

2
??

2