#include <stdio.h>
#include <string.h>
#define N 300
#define L 1000000
#define MD 1000000007
int max(int a, int b) { return a > b ? a : b; }
int ans[N + 1];
void init() {
static int dp[N + 1][N * 2 + 1], dq[N + 1][N * 2 + 1];
int n, a, a_, b, b_;
dp[0][0] = 1;
ans[0] = 1;
for (n = 1; n <= N; n++) {
for (a = 0; a <= n; a++)
memset(dq[a], 0, (n * 2 + 1) * sizeof *dq[a]);
for (a = 0; a <= n - 1; a++)
for (b = 0; b <= (n - 1) * 2; b++) {
int x = dp[a][b];
a_ = a + 1, b_ = b + 2;
dq[a_][b_] = (dq[a_][b_] + x) % MD;
if (b > 0) {
a_ = max(a - 2, 0), b_ = b - 1;
dq[a_][b_] = (dq[a_][b_] + x) % MD;
}
}
for (a = 0; a <= n; a++)
memcpy(dp[a], dq[a], (n * 2 + 1) * sizeof *dq[a]);
for (b = 0; b <= n * 2; b++)
ans[n] = (ans[n] + dp[0][b]) % MD;
}
}
int main() {
int mode, t;
scanf("%d%d", &mode, &t);
init();
while (t--)
if (mode == 1) {
static char cc[L + 1];
static int aa[L + 1], bb[L + 1];
int l, h, bad, d;
scanf("%s", cc), l = strlen(cc);
bad = 0;
aa[0] = bb[0] = 0;
for (h = 0; h < l; h++)
if (cc[h] == '(')
aa[h + 1] = aa[h] + 1, bb[h + 1] = bb[h] + 2;
else {
if (bb[h] == 0) {
bad = 1;
break;
}
aa[h + 1] = max(aa[h] - 2, 0), bb[h + 1] = bb[h] - 1;
}
if (bad || aa[l] > 0)
printf("impossible\n");
else {
d = 0;
for (h = l - 1; h >= 0; h--)
if (cc[h] == '(') {
if (d - 1 <= bb[h])
cc[h] = d % 2 == 0 ? 'B' : 'R', d--;
else
cc[h] = 'G', d -= 2;
} else {
if (d + 1 >= aa[h])
cc[h] = d % 2 == 0 ? 'R' : 'B', d++;
else
cc[h] = 'G', d += 2;
}
printf("%s\n", cc);
}
} else {
int n;
scanf("%d", &n);
printf("%d\n", ans[n]);
}
return 0;
}
