#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const string IMPOSSIBLE = "impossible";
const int MOD = (int) 1e9 + 7;
enum Color {
GREEN = 'G',
RED = 'R',
BLUE = 'B',
};
template<class F>
string filter(const string& s, const F& pred) {
string ret;
for (int i = 0; i < (int) s.length(); ++i) {
if (pred(i, s[i])) {
ret += s[i];
}
}
return ret;
}
bool check(string s) {
int balance = 0;
for (char c: s) {
if (c == '(') {
balance++;
} else {
balance--;
if (balance < 0) {
return false;
}
}
}
return balance == 0;
}
string reconstruct(string s) {
int n = (int) s.length();
vector<Color> color(n, Color::GREEN);
vector<int> greenOpen, greenClosed;
int balance = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '(') {
greenOpen.push_back(i);
balance++;
} else {
balance--;
greenClosed.push_back(i);
if (balance < 0) {
balance = 0;
if (greenClosed.size() < 2U) {
return IMPOSSIBLE;
}
int pos1 = greenClosed.back();
greenClosed.pop_back();
int pos2 = greenClosed.back();
greenClosed.pop_back();
color[pos1] = Color::RED;
color[pos2] = Color::BLUE;
}
}
}
while (balance-- > 0) {
if (greenOpen.size() < 2U) {
return IMPOSSIBLE;
}
int pos1 = greenOpen.back();
greenOpen.pop_back();
int pos2 = greenOpen.back();
greenOpen.pop_back();
color[pos1] = Color::RED;
color[pos2] = Color::BLUE;
}
string s1 = filter(s, [&color](int index, char c) -> bool {
return color[index] == Color::RED || color[index] == Color::GREEN;
});
string s2 = filter(s, [&color](int index, char c) -> bool {
return color[index] == Color::BLUE || color[index] == Color::GREEN;
});
string ans;
for (int i = 0; i < n; ++i) {
ans += (char) color[i];
}
return (check(s1) && check(s2)) ? ans: IMPOSSIBLE;
}
vector<int> count(int n) {
vector<vector<int>> dp(n + 5, vector<int>(2 * n + 5, 0));
auto ndp = dp;
vector<int> ans(n + 1);
ans[0] = 1;
dp[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (auto& v: ndp) {
fill(v.begin(), v.end(), 0);
}
for (int left = 0; left <= n; ++left) {
for (int right = left; right <= 2 * i; ++right) {
ndp[left + 1][right + 2] += dp[left][right];
ndp[left + 1][right + 2] %= MOD;
int nLeft = max(0, left - 2);
int nRight = right - 1;
if (nLeft <= nRight) {
ndp[nLeft][nRight] += dp[left][right];
ndp[nLeft][nRight] %= MOD;
}
}
}
ndp.swap(dp);
ans[i] = 0;
for (int right = 0; right <= 2 * i; ++right) {
ans[i] += dp[0][right];
ans[i] %= MOD;
}
}
return ans;
}
int main() {
int type;
cin >> type;
if (type == 1) {
int T;
cin >> T;
while (T-- > 0) {
string s;
cin >> s;
cout << reconstruct(move(s)) << '\n';
}
} else {
int T;
cin >> T;
vector<int> qs(T);
for (int& x: qs) {
cin >> x;
}
vector<int> ans = count(*max_element(qs.begin(), qs.end()));
for (int x: qs) {
cout << ans[x] << '\n';
}
}
}
