首先，P R Q 的情况是很容易的，分类讨论一下就行了，Q 的部分有点细节，不过都挺 trivial。
先解决 B 的部分。我们枚举第一步是向左走还是向右走，假设是左，右的部分把 \(x,y\) 分别变为 \(m-x+1\) 和 \(m-y+1\) 再做一遍就行了。最少步数显然是你每次一直朝一个方向走，撞到墙就反弹。因此我们先考虑要变换多少次方向才能到达第 \(r\) 行，假设是 \(cnt\)，以及我们如果严格遵守上述“撞到墙就反弹”的策略，撞墙之后会到达第 \(r\) 行的哪一列，假设为 \(t\)。那么如果我们最后一步是向右下走，并且 \(y\ge t\)，或者最后一步向左下走，并且 \(y\le t\)，那么最少步数就是 \(cnt+1\)，否则需要再拐个弯，最少步数是 \(cnt+2\)。接下来考虑计算方案数。实际上最小方案数就相当于在最理想化的方案的基础上，每次拐弯可以向里收缩若干步。这是经典的插板法模型，直接组合数解决。因为下指标 \(\le m\)，因此直接 \(O(m)\) 计算就好了。
最后考虑 K 的部分。这一部分貌似有很多种做法，我参考的是 feecle6418 的做法。\(O(m^3\log n)\) 的矩阵快速幂是显然的，但是过不去。一种优化的基于特征多项式的线性递推，因为矩阵比较有特点所以貌似是可以做的，但是我没有细想。考虑发掘一下这个矩阵的性质。有 \(\forall n\in\text{Z}^*,1\le i,j\le m\)：
- \(A^n_{i,j}=A^n_{j,i}\)。
- \(A^n_{i,j}=A^n_{m-i+1,m-j+1}\)。
- \(A^n_{i,j}=A^n_{i-1,j-1}+A^n_{1,i+j-1}\)（\(i+j\le m+1\)）
前两个性质的证明是显然的，考虑第三个性质。可能有基于组合的做法，但是我没有想到。
归纳证明，\(i=1\) 显然成立（越界的部分值一律看作 \(0\)），假设 \(i\) 成立，考虑推到 \(i+1\)。
对于 \(i+j+1\le m+1\) 的 \(i,j\)，考虑 \(A^{n+1}_{i,j}\) 与 \(A^{n+1}_{j,i}\)，得 \(A^{n+1}_{i,j}=A^n_{i,j}+A^n_{i,j-1}+A^n_{i,j+1}=A^n_{j,i-1}+A^n_{j,i}+A^n_{j,i+1}=A^{n+1}_{j,i}\)。
消去左右两边相同的 \(A^n_{i,j},A^n_{j,i}\)，得 \(A^n_{i,j-1}+A^n_{i,j+1}=A^n_{j,i-1}+A^n_{j,i+1}(*)\)。
而由于 \(i\) 成立且 \(i+j+1\le m+1\)，因此 \(A^n_{i,j+1}=A^{n}_{i-1,j}+A^n_{1,i+j}\)。
故对 \((*)\) 式移项可得 \(A^n_{i+1,j}=A^n_{i,j-1}+(A^n_{i,j+1}-A^n_{i-1,j})=A^n_{i,j-1}+A^n_{1,i+j}\)，故 \(i+1\) 也成立。
有了性质三，在矩阵乘法的时候我们实际上只需要计算出第一行，就可以 \(O(m^2)\) 地推出其余的部分了。这样总复杂度 \(O(m^2\log n)\)。
const int MAXN=1000;
const int MOD=1e9+7;
void add(int &x,int v){((x+=v)>=MOD)&&(x-=MOD);}
int n,m,inv[MAXN+5];
int binom(int n,int k){
int res=1;
for(int i=1;i<=k;i++)res=1ll*res*(n-i+1)%MOD*inv[i]%MOD;
return res;
}
int calc(int x,int y){return binom(x+y-1,x);}
pii calc_bishop(int x,int y){
if(x==1)return mp(MOD,0);
if(x==m&&y==1&&n==m)return mp(1,1);
int lft=n-x,nd=(lft+m-2)/(m-1),tt=(lft+m-2)%(m-1)+2,flg;
if(nd%2==0)tt=m+1-tt,flg=(tt<y);
else flg=(tt>y);
if(flg)return mp(nd+2,calc((tt>y)?(m-y-(tt-y)/2):(y-1-(y-tt)/2),nd+1));
else return mp(nd+1,calc(abs(tt-y)/2,nd));
}
struct mat{
int a[MAXN+5][MAXN+5];
mat(){memset(a,0,sizeof(a));}
}ans;
mat add1(mat x){
mat res;
for(int i=1;i<=m;i++)for(int j=1;j<=m;j++){
if(j!=1)add(res.a[i][j-1],x.a[i][j]);
add(res.a[i][j],x.a[i][j]);
if(j!=m)add(res.a[i][j+1],x.a[i][j]);
}return res;
}
mat mul2(mat x){
mat res;
for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)
res.a[1][j]=(res.a[1][j]+1ll*x.a[1][i]*x.a[i][j])%MOD;
for(int i=2;i<=m;i++)for(int j=1;i+j<=m+1;j++)
res.a[i][j]=(res.a[i-1][j-1]+res.a[1][i+j-1])%MOD;
for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)if(i+j>m+1)
res.a[i][j]=res.a[m-i+1][m-j+1];
return res;
}
void init(){
int tmp=n-1;vector<int>vec;
while(tmp){
if(tmp&1)vec.pb(1);
vec.pb(2);tmp>>=1;
}reverse(vec.begin(),vec.end());
// for(int x:vec)printf("%d ",x);printf("\n");
for(int i=1;i<=m;i++)ans.a[i][i]=1;
for(int x:vec){
if(x==1)ans=add1(ans);
else ans=mul2(ans);
}
}
void solve(){
static char opt[5];scanf("%s",opt+1);
if(opt[1]=='P'){
int x,y;scanf("%d%d",&x,&y);
if(x==y)printf("%d %d\n",n-1,1);
else puts("0 0");
}else if(opt[1]=='R'){
int x,y;scanf("%d%d",&x,&y);
if(x==y)puts("1 1");
else puts("2 2");
}else if(opt[1]=='Q'){
int x,y;scanf("%d%d",&x,&y);
if(x==y||abs(x-y)==n-1)puts("1 1");
else{
int res=4;
if((1+x)%2==(n+y)%2){
if((x+y-n+1)/2>=1)res++;
if((x+y+n-1)/2<=m)res++;
}
if((x==1||x==m||y==1||y==m)&&(n==m))res++;
printf("2 %d\n",res);
}
}else if(opt[1]=='B'){
int x,y;scanf("%d%d",&x,&y);
if((1+x)%2!=(n+y)%2){puts("0 0");return;}
pii p1=calc_bishop(x,y);
pii p2=calc_bishop(m-x+1,m-y+1);
if(p1.fi<p2.fi)printf("%d %d\n",p1.fi,p1.se);
else if(p1.fi>p2.fi)printf("%d %d\n",p2.fi,p2.se);
else printf("%d %d\n",p1.fi,(p1.se+p2.se)%MOD);
}else{
int x,y;scanf("%d%d",&x,&y);
printf("%d %d\n",n-1,ans.a[x][y]);
}
}
int main(){
for(int i=(inv[0]=inv[1]=1)+1;i<=MAXN;i++)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
int qu;scanf("%d%d%d",&n,&m,&qu);init();while(qu--)solve();
return 0;
}