#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end()
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;
ostream& operator<<(ostream& os, string o) {
for (char c : o) os << c;
return os;
}
template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
os << "{";
int g = size(o);
for (auto i : o) os << i << ((--g) == 0 ? "" : ", ");
os << "}";
return os;
}
void _print() {
cerr << "\n";
}
template<typename T, typename ...V>
void _print(T t, V... v) {
cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);
}
#ifdef LOCAL
#define dbg(x...) cerr << #x << " = "; _print(x);
#else
#define dbg(x...)
#define cerr if (0) std::cerr
#endif
/*
P = 1:
"greedily open" some prefix
and then "greedily close" some suffix
if at some point there is a valid "turning point", then we can colour
assign a first
P = 2:
some sequence is rgb-readable if and only if there exists a greedy prefix + suffix of assignments
there cannot be two greedy prefix/suffix assignments since it would throw off the balance
compute # of greedy assignments for each prefix and each suffix
dp[i][j] = # of ways to greedy assign first i parenthesis such that there are j open parenthesis
rdp[i][j] # of ways to greedy assign the 1-indexed suffix such that there are j closed parenthesis
*/
const ll mod = 1e9 + 7;
void add(ll& a, ll b) {
a += b;
a -= (a >= mod) * mod;
a += (a < 0) * mod;
}
const ll bruh[2] = {1, -1};
ll solve2() {
ll n; cin >> n;
vt<vt<ll>> dp(n + 1, vt<ll>(n + 1));
auto rdp = dp;
dp[0][0] = 1;
F0R (i, n) {
F0R (j, n) {
// assign open
add(dp[i + 1][j + 1], dp[i][j]);
// assign closed
ll cur_closed = i - j;
if (2 * j - (cur_closed + 1) >= 0) {
add(dp[i + 1][j], dp[i][j]);
}
}
}
rdp[n][0] = 1;
ROF (i, 1, n + 1) {
F0R (j, n) {
// assign closed
add(rdp[i - 1][j + 1], rdp[i][j]);
// assign open
ll cur_open = n - i - j;
if (2 * j - (cur_open + 1) >= 0) {
add(rdp[i - 1][j], rdp[i][j]);
}
}
}
ll ans = 0;
F0R (i, n + 1) {
F0R (j, i + 1) {
ll cur_offset = 2 * j - (i - j);
ll rem = n - i;
ll req_closed = cur_offset + rem;
if (req_closed % 3 != 0 || req_closed < 0) continue;
req_closed /= 3;
if (req_closed > n) continue;
add(ans, (dp[i][j] * rdp[i][req_closed]) % mod);
}
}
return ans;
}
string solve1() {
string st; cin >> st;
int n = size(st);
vt<int> seq(n);
F0R (i, n) seq[i] = st[i] == '(' ? 1 : -1;
vt<pi> pfx(n + 1), sfx(n + 1);
F0R (i, n) {
pi prv = pfx[i];
if (seq[i] == 1) prv.f++, prv.s++;
else {
if (prv.f == prv.s) prv.f--;
else prv.s--;
}
if (prv.f < 0 || prv.s < 0) prv = {-inf, -inf};
pfx[i + 1] = prv;
}
ROF (i, 0, n) {
pi prv = sfx[i + 1];
if (seq[i] == -1) prv.f++, prv.s++;
else {
if (prv.f == prv.s) prv.f--;
else prv.s--;
}
if (prv.f < 0 || prv.s < 0) prv = {inf, inf};
sfx[i] = prv;
}
F0R (i, n + 1) {
if (pfx[i].f == sfx[i].f && pfx[i].s == sfx[i].s) {
// answer
string out = "";
string rout = "";
int x = 0, y = 0;
F0R (j, i) {
if (seq[j] == 1) {
x++, y++;
out += 'G';
} else {
if (x == y) out += 'R', x--;
else out += 'B', y--;
}
}
x = y = 0;
ROF (j, i, n) {
if (seq[j] == -1) {
x--, y--;
rout += 'G';
} else {
if (x == y) rout += 'R', x++;
else rout += 'B', y++;
}
}
reverse(all(rout));
out += rout;
return out;
}
}
return "impossible";
}
main() {
cin.tie(0)->sync_with_stdio(0);
int p, t; cin >> p >> t;
if (p == 1) {
F0R (i, t) cout << solve1() << endl;
} else if (p == 2) {
F0R (i, t) cout << solve2() << endl;
}
}
