#include <bits/stdc++.h>
using namespace std;
string solve1(string s = "") {
if (s.empty())
cin >> s;
int n = s.length();
stack<int> pos, neg;
int pcnt = 0;
string ans(n, 'G');
for (int i = 0; i < n; i++) {
if (s[i] == '(')
pos.push(i), pcnt++;
else {
neg.push(i);
if (pcnt == 0) {
if (neg.size() < 2)
return "impossible";
ans[neg.top()] = 'R';
neg.pop();
ans[neg.top()] = 'B';
neg.pop();
}
else
pcnt--;
}
}
if (2 * pcnt > pos.size())
return "impossible";
for (int i = 0; i < pcnt; i++) {
ans[pos.top()] = 'R';
pos.pop();
ans[pos.top()] = 'B';
pos.pop();
}
int sum1 = 0, sum2 = 0;
for (int i = 0; i < n; i++) {
if (ans[i] == 'R' || ans[i] == 'G')
sum1 += s[i] == '(' ? 1 : -1;
if (ans[i] == 'B' || ans[i] == 'G')
sum2 += s[i] == '(' ? 1 : -1;
if (sum1 < 0 || sum2 < 0)
return "impossible";
}
return ans;
}
constexpr int MAXN = 301, MOD = 1e9 + 7;
int solve2() {
static int mem[MAXN], dp[MAXN + 5][MAXN + 5][MAXN + 5];
if (dp[0][0][0] == 0) {
dp[0][0][0] = 1;
for (int i = 1; i < MAXN; i++) {
for (int j = 0; j < MAXN; j++) {
for (int k = 0; k < MAXN; k++) {
if (k)
dp[i][j][k] += dp[i - 1][j][k - 1], dp[i][j][k] %= MOD;
else {
dp[i][j][k] += dp[i - 1][j + 1][k];
dp[i][j][k] %= MOD;
if (j)
dp[i][j][k] += dp[i - 1][j - 1][k + 1], dp[i][j][k] %= MOD;
}
if (j > 2)
dp[i][j][k] += dp[i - 1][j - 3][k + 2], dp[i][j][k] %= MOD;
}
}
}
}
int n;
cin >> n;
if (mem[n])
return mem[n];
int ans = 0;
for (int j = 0; j < MAXN; j++)
ans += dp[n][j][0];
return mem[n] = ans;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int p, t;
cin >> p >> t;
while (t--) {
if (p == 1)
cout << solve1() << '\n';
if (p == 2)
cout << solve2() << '\n';
}
}
