| 2026-2027 ICPC NERC (NEERC), North-Western Russia Regional Contest (Northern Subregionals) |
|---|
| Закончено |
Fiona has $$$n$$$ stamps, numbered from $$$1$$$ to $$$n$$$. Stamp $$$i$$$ prints a non-empty string $$$s_i$$$ of round brackets: '(' and ')'. Different stamps may print the same string.
She is creating an artwork on four pieces of paper arranged in a row. On each piece, Fiona uses one of the stamps to print exactly one copy of its string. She may use the same stamp for several pieces. Fiona does not rotate or flip the stamps when printing. The four printed strings are concatenated from left to right.
A string of round brackets is a correct bracket sequence if it contains equally many opening and closing brackets, and every prefix contains at least as many opening brackets as closing ones. For example, "()()" and "(())" are correct, while ")(" and "(()" are not.
In how many ways can Fiona choose which stamp to use for each piece so that the resulting string is a correct bracket sequence? Two ways are considered different if they use different stamps for at least one piece. Since this number can be large, find it modulo $$$998\,244\,353$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The first line of each test case contains an integer $$$n$$$, denoting the number of stamps ($$$2 \le n \le 2 \cdot 10^5$$$).
The $$$i$$$-th of the following $$$n$$$ lines contains the non-empty string $$$s_i$$$ printed by stamp $$$i$$$. Each string consists only of the characters '(' and ')'. The sum of the lengths of the strings does not exceed $$$2 \cdot 10^6$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$, and the sum of the lengths of all strings over all test cases does not exceed $$$2 \cdot 10^6$$$.
For each test case, print the number of ways to choose a stamp for each of the four pieces so that the concatenation is a correct bracket sequence, modulo $$$998\,244\,353$$$.
23(()))((())3()()
169
In the first test case, no valid choice uses stamp $$$2$$$. Fiona can choose either stamp $$$1$$$ or stamp $$$3$$$ for each of the four pieces. This gives $$$2^4 = 16$$$ ways, even though they all produce the same string.
In the second test case, stamp $$$3$$$ is used an even number of times in any valid choice. Using it four times gives one way. If stamp $$$3$$$ is used twice, there are six ways to choose the two pieces on which it is used. The leftmost of the two remaining pieces must use stamp $$$1$$$, and the other must use stamp $$$2$$$. If stamp $$$3$$$ is not used, the possible strings are "(())" and "()()". Thus, the answer is $$$1+6+2=9$$$.
| Название |
|---|


