Problem Description

Translated from BalkanOI 2018 Day 2 T1 “Parentrises”.

A parentheses string is a string consisting only of ( and ). If inserting some 1 and + into a parentheses string can turn it into a correct expression, then the string is a balanced parentheses string. For example, (()) and ()() are balanced parentheses strings, while )( and ( are not. The empty string is considered a balanced parentheses string. (This is the one you saw when learning Catalan numbers.)

Color each parenthesis of a parentheses string (not necessarily balanced) with one of three colors: red, green, and blue. If there exists a coloring such that all of the following are true:

• After ignoring all blue parentheses in the string, it becomes a balanced parentheses string.
• After ignoring all red parentheses in the string, it becomes a balanced parentheses string.

Then the string is called RGB-readable.

You will receive one of two types of tasks. The task type is given by an integer $P$, where $P = 1$ or $2$.

• $P = 1$: You will receive $T$ queries, each containing a parentheses string. Determine whether the string is RGB-readable. If it is, output one valid coloring; otherwise output impossible.
• $P = 2$: You will receive $T$ queries, each containing an integer $N$. Compute how many RGB-readable balanced parentheses strings of length $N$ there are. Output the answer modulo $(10^9+7)$.

Input Format

The first line contains an integer $P$.
The second line contains an integer $T$.

• If $P = 1$, then in the next $T$ lines, each line contains a parentheses string representing a query.
• If $P = 2$, then in the next $T$ lines, each line contains an integer $N$ representing a query.

Output Format

If $P = 1$, for each query:

• If the string is RGB-readable, output one valid coloring.
• If the string is not RGB-readable, output impossible.

If $P = 2$, for each query, output the number of RGB-readable balanced parentheses strings of length $N$ modulo $(10^9+7)$.

1
3
())(()
()(()
()))

GRBRBG
BBRBG
impossible

2
2
6
100

12
959772055

Hint

Explanation for Sample $1$:

For query 1, after ignoring all blue parentheses, the original string becomes ()(); after ignoring all red parentheses, it also becomes ()().
For query 2, after ignoring all blue parentheses, it becomes (); after ignoring all red parentheses, it becomes ()().

Constraints for $P = 1$:
Let $L$ be the total length of all strings.

• Subtask #1 (5 points): $1 \le T \le 5$, $1 \le len(S) \le 13$.
• Subtask #2 (11 points): $1 \le L \le 100$.
• Subtask #3 (6 points): $1 \le L \le 1000$.
• Subtask #4 (28 points): $1 \le L \le 10^6$.

Constraints for $P = 2$:

• Subtask #5 (6 points): $1 \le N, T \le 15$.
• Subtask #6 (16 points): $1 \le N, T \le 30$.
• Subtask #7 (28 points): $1 \le N, T \le 300$.

Thanks to Planet6174 for providing the translation.

Translated by ChatGPT 5