P4788 [BalkanOI 2018] Parentrises

**翻译自 [BalkanOI 2018](http://boi2018.ro) Day2 T1「[Parentrises](http://boi2018.ro/assets/Tasks/BOI/Day_2/parentrises/parentrises_en.pdf)」** **「括号串」**是一个仅由 `(` 和 `)` 构成的字符串。如果在括号串中插入一些 `1` 和 `+` 可以将其转化为正确的表达式，该字符串就是一个**「良括号串」**。例如，`(())` 和 `(())` 是良括号串，而 `)(` 和 `(` 不是。空字符串可视为良括号串。（就是你们学 Catalan 数时学的那个啊） 将一个**括号串**（不是良括号串）的每个括号都涂成红绿蓝三种颜色之一，如果有一种方案同时满足： + 忽略该串的所有蓝色括号后它是**良括号串**； + 忽略该串的所有红色括号后它是良括号串； 该串就是 **RGB 可读**的。 你会接到两类任务之一。任务类型用一个整数 $P$ 表示，$P=1$ 或 $2$。 * $P=1$：你会接到 $T$ 组询问，每组询问包含一个括号串，试问该串是否 RGB 可读，如果是，请输出一种染色方案，如果否请输出 `impossible`； * $P=2$：你会接到 $T$ 组询问，每组询问包含一个数 $N$，试求：有多少个长度为 $N$ 的 RGB 可读的良括号串。输出答案模 $(10^9+7)$ 的结果。

第一行有一个整数 $P$。 第二行有一个整数 $T$。 + 如果 $P=1$，在接下来的 $T$ 行中，每行有一个括号串，表示询问。 + 如果 $P=2$，在接下来的 $T$ 行中，每行有一个数 $N$，表示询问。

如果 $P=1$，对于每组询问， + 如果该串是 RGB 可读的，请输出一种染色方案； + 如果该串不是 RGB 可读的，请输出 `impossible`； 如果 $P=2$，对于每组询问，请输出长度为 $N$ 的 RGB 可读的良括号串的个数模 $(10^9+7)$ 的结果。

样例 $1$ 解释： 对于查询 1，忽略原串的所有蓝色括号后它变为 `()()`；忽略原串的所有红色括号后它也变为 `()()`。 对于查询 2，忽略原串的所有蓝色括号后它变为 `()`；忽略原串的所有红色括号后它变为 `()()`。 $P = 1$： 设 $L$ 为字符串总长。 * 子任务 #1（5 分）：$1 ≤ T ≤ 5,$ $1 ≤ len(S) ≤ 13$。 * 子任务 #2（11 分）：$1 ≤ L ≤ 100$。 * 子任务 #3（6 分）：$1 ≤ L ≤ 1000$。 * 子任务 #4（28 分）：$1 ≤ L ≤ 10^6$。 $P = 2$： * 子任务 #5（6 分）：$1 ≤ N, T ≤ 15$。 * 子任务 #6（16 分）：$1 ≤ N, T ≤ 30$。 * 子任务 #7（28 分）：$1 ≤ N, T ≤ 300$。 感谢 Planet6174 提供的翻译