http://acm.hdu.edu.cn/showproblem.php?pid=5063
只有50个询问，50个操作逆推回去即可，注意mul每次要*2%(modo
- 1)因为是指数！
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define clr0(x) memset(x,0,sizeof(x))
typedef long long LL; int n,m;
const double pi = acos ( -1.0 ) ;
const LL modo = 1000000007;
int op[100005],op_n;
LL ans[55];
int ans_n;
LL quick_pow(LL a,int b)
{
LL c = 1;
while(b){
if(b&1)
c = (c*a)%modo;
b>>=1;
a = (a*a)%modo;
}
return c;
}
LL gao(LL x)
{
int mul = 1;
for(int i = op_n - 1;i >= 0;--i){
if(op[i] == 1){
// 1,3,5->1,2,3
// 2,4,6->4,5,6 // 1,3,5,7->1,2,3,4
// 2,4,6->5,6,7
if(x <= (n+1)/2)
x = x*2 - 1;
else
x = (x - (n+1)/2)<<1;
}
else if(op[i] == 2){
x = n + 1 - x;
}
else{
mul = (mul*2)%(modo-1);
}
}
return quick_pow(x,mul);
}
void work()
{
op_n = ans_n = 0;
LL x;
char q[2];
while(m--){
scanf("%s%I64d",q,&x);
if(q[0] == 'O'){
op[op_n++] = (int)x;
}else{
ans[ans_n++] = gao(x);
}
}
for(int i = 0;i < ans_n;++i)
printf("%I64d\n",ans[i]);
return;
}
int main () {
int T;
RD(T);
while(T--){
RD2(n,m);
work();
}
return 0 ;
}