// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
const ll Mod = 1000000007LL;
const int N = 3e2 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;
str Solve1(){
vector<int> O, C;
int sm = 0;
str s;
cin >> s;
int n = s.size();
vector<int> mk(n, 0);
for(int i = 0; i < n; i++){
if(s[i] == '('){
O.pb(i);
sm ++;
} else {
C.pb(i);
sm --;
}
}
reverse(all(C));
str Im = "impossible";
int Ao = (sm <= 0 ? -sm: 0);
int Ac = (sm >= 0 ? sm: 0);
int idx = -1;
for(int i = 0; i < n; i++){
if(Ao + i > (int)O.size()) break;
if(Ac + i > (int)C.size()) break;
int po = (Ao + i == 0 ? -1 : O[Ao + i - 1]);
int pc = (Ac + i == 0 ? n : C[Ac + i - 1]);
if(po >= pc) break;
idx = i;
}
//debug(idx);
if(idx == -1) return Im;
for(int i = 0; i < Ao + idx; i++) mk[O[i]] = 1;
for(int i = 0; i < Ac + idx; i++) mk[C[i]] = 1;
str res = "";
int Sr = 0, Sb = 0;
for(int i = 0; i < n; i++){
if(mk[i]){
res += "G";
if(s[i] == '('){
Sr ++;
Sb ++;
} else {
Sr --;
Sb --;
}
} else {
if(s[i] == '('){
if(Sr < Sb) Sr ++, res += "R";
else Sb ++, res += "B";
} else {
if(Sr > Sb) Sr --, res += "R";
else Sb --, res += "B";
}
}
if(min(Sr, Sb) < 0) return Im;
}
assert(Sr == 0); assert(Sb == 0);
return res;
}
ll dp[N][N][3];
ll ans[N];
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
dp[1][2][0] = 1;
dp[1][1][1] = 1;
for(int i = 1; i + 1 < N; i++){
for(int sm = 0; sm < N; sm ++){
dp[i][sm][0] %= Mod;
dp[i][sm][1] %= Mod;
dp[i][sm][2] %= Mod;
if(dp[i][sm][0]){
if(sm + 1 < N) dp[i + 1][sm + 1][1] += dp[i][sm][0];
if(sm + 2 < N) dp[i + 1][sm + 2][0] += dp[i][sm][0];
if(sm >= 1) dp[i + 1][sm - 1][0] += dp[i][sm][0];
if(sm >= 2) dp[i + 1][sm - 2][2] += dp[i][sm][0];
}
if(dp[i][sm][1]){
if(sm + 1 < N) dp[i + 1][sm + 1][1] += dp[i][sm][1];
//dp[i + 1][sm + 2][0] += dp[i][sm][0];
//if(sm >= 1) dp[i + 1][sm - 1][0] += dp[i][sm][0];
if(sm >= 2) dp[i + 1][sm - 2][2] += dp[i][sm][1];
}
if(dp[i][sm][2]){
if(sm + 1 < N) dp[i + 1][sm + 1][2] += dp[i][sm][2];
//dp[i + 1][sm + 2][0] += dp[i][sm][2];
//if(sm >= 1) dp[i + 1][sm - 1][0] += dp[i][sm][2];
if(sm >= 2) dp[i + 1][sm - 2][2] += dp[i][sm][2];
}
}
ans[i] = (dp[i][0][0] + dp[i][0][1] + dp[i][0][2]) % Mod;
}
int PR;
cin >> PR;
int T;
cin >> T;
while(T --){
if(PR == 1) cout << Solve1() << '\n';
else {
int m;
cin >> m;
cout << ans[m] << '\n';
}
}
return 0;
}
