题目描述

如何将两题拼成一题.jpg

翻译自 BalkanOI 2018 Day2 T1「Parentrises」

「括号串」是一个仅由 ( 和 ) 构成的字符串。如果在括号串中插入一些 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
3
())(()
()(()
()))

GRBRBG
BBRBG
impossible

对于查询 1，忽略原串的所有蓝色括号后它变为 ()()；忽略原串的所有红色括号后它也变为 ()()。 对于查询 2，忽略原串的所有蓝色括号后它变为 ()；忽略原串的所有红色括号后它变为 ()()。

2
2
6
100

12
959772055

数据范围与提示

$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$。

感谢 applese 提供 SPJ。