做题感悟：这题开始以为是找规律，果断悲剧阿，最后才意识到应该逆着退回去。
解题思路：
这题的突破口就是要逆向推回去，这样复杂度为 50 * m 的复杂度。做完这题还学到一点就是如果取模的数为素数，可以让指数先对素数减一取模，取模后指数就比较小了。
代码：
#include<iostream>
#include<sstream>
#include<map>
#include<cmath>
#include<fstream>
#include<queue>
#include<vector>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<stack>
#include<bitset>
#include<ctime>
#include<string>
#include<cctype>
#include<iomanip>
#include<algorithm>
using namespace std ;
#define INT __int64
#define L(x) (x * 2)
#define R(x) (x * 2 + 1)
const int INF = 0x3f3f3f3f ;
const double esp = 0.0000000001 ;
const double PI = acos(-1.0) ;
const INT mod = 1e9 + 7 ;
const int MY = 1e7 + 5 ;
const int MX = 100000 + 5 ;
int n ,m ;
struct node
{
int x ,y ;
}T[MX] ;
INT pow(INT a ,int k ,INT mod)
{
INT b = 1 ;
while(k)
{
if(k&1)
b = (b*a)%mod ;
a = (a*a)%mod ;
k>>= 1 ;
}
return b ;
}
int main()
{
//freopen("input.txt" ,"r" ,stdin) ;
int Tx ;
scanf("%d" ,&Tx) ;
while(Tx--)
{
scanf("%d%d" ,&n ,&m) ;
memset(T ,0 ,sizeof(T)) ;
char ch ; int x ,temp ;
for(int i = 0 ;i < m ; ++i)
{
cin>>ch>>x ;
if(ch == 'Q')
T[i].x = 1 ;
T[i].y = x ;
}
for(int i = 0 ;i < m ; ++i)
if(T[i].x)
{
int num = 0 ,St = T[i].y ;
for(int j = i ;j >= 0 ; --j)
{
if(T[j].x) continue ;
if(T[j].y == 1)
{
if(n%2) temp = n/2 + 1 ;
else temp = n/2 ;
if(St <= temp)
St = St*2 - 1 ;
else St = (St - temp)*2 ;
}
else if(T[j].y == 2)
St = n - St + 1 ;
else num++ ;
}
if(!num) cout<<St<<endl ;
else
cout<<pow((INT)St ,pow(2 ,num ,mod-1) ,mod)<<endl ;
}
}
return 0 ;
}