P4788 [BalkanOI 2018] Parentrises

**Translated from [BalkanOI 2018](http://boi2018.ro) Day 2 T1 “[Parentrises](http://boi2018.ro/assets/Tasks/BOI/Day_2/parentrises/parentrises_en.pdf)”.** 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)$.

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.

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)$.

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