定义集合\(S\)由同时满足以下条件的\(x\)构成：
- \([1,x)\)中\(\le a_{x}\)的元素 和 \((x,n]\)中\(\ge a_{x}\)的元素 构成递增子序列
- \([1,x)\)中\(\ge a_{x}\)的元素 和 \((x,n]\)中\(\le a_{x}\)的元素 构成递减子序列
性质1：\(a\)为完美数组当且仅当\(S\ne \empty\)
必要性：注意\(x\in S\)是\(x\)可以染成红色和绿色的必要条件
充分性：任取\(x\in S\)，将条件中第\(1\)类元素染成红色，其余染成绿色即可
性质2：若\(x\in S\)，则\(x+1\in S\iff \forall i\in [1,x),a_{i}\not\in [a_{x},a_{y}]\cup [a_{y},a_{x}]\)
性质3：记\(\begin{cases}l=\min_{x\in S}x\\r=\max_{x\in S}x\end{cases}\)，则\(S=[l,r]\cap Z\)且满足以下条件之一
- \(l+1=r\)且\(a_{l}=a_{r}\)
- \(a_{l}<a_{l+1}<...<a_{r}\)或\(a_{l}>a_{l+1}>...>a_{r}\)
（证明可以自行分类讨论得到）
为了方便，以下均假设为第\(2\)种情况，第\(1\)种情况是类似的
根据性质\(3\)，在\(r\)处统计方案数，即要求\(r+1\not\in S\)，这可以用性质\(2\)判定
注意到对于\(a_{[1,r)}\)，恰存在一种染色方式使得红色的结尾\(<a_{r}\)且绿色的结尾\(>a_{r}\)
定义\(f_{i,x,y}\)表示前\(i\)个位置中两序列结尾分别为\(x,y\)的方案数，转移易优化至\(O(nm^{2})\)，后缀类似
枚举\(r,a_{r}\)和\(a_{r+1}\)后，即求形如\(\sum_{x\le x_{0}}\sum_{y\ge y_{0}}f_{i,x,y}\)，预处理即可，时间复杂度为\(O(tnm^{2})\)
性质4：得分最大的染色方案形如
- \([1,r)\)中\(\le a_{r}\)的元素 和 \((r,n]\)中\(\ge a_{r}\)的元素 染成红色
- \([1,r)\)中\(\ge a_{r}\)的元素 和 \((r,n]\)中\(\le a_{r}\)的元素 染成绿色
- \(a_{r}\)的颜色取染红色或绿色中的较大值
此时，将贡献拆开，得分分为以下几部分：
-
\(a_{[1,r)}\)中，用\(g/g0/g1_{i,x,y}\)表示……的得分和、红色数和 和 绿色数和 即可
-
\(a_{r}\)中，用\(f'_{i,z,x,y}\)表示在\(f_{i,x,y}\)的基础上红色有\(z\)个的方案数即可
-
\(a_{(r,n]}\)中，其内部无贡献，仅与\(a_{[1,r)}\)之间有贡献
以染成红色的\(a_{i}\)为例，即统计\(a_{[1,r)}\)中\(>a_{i}\)的元素个数，枚举\(a_{i}\)即可
时间复杂度为\(O(tn^{2}m^{2}+tnm^{3})\)，大概不是标算，但卡卡常应该能过（雾
（以下代码并没有卡常，正确性仅保证过大样例）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=55,M=205,mod=998244353;
int t,n,m,n0,ans1,ans2,a[N];
int fs[N][M][M],Fp[N][N][M][M],gp0[N][M][M],gp1[N][M][M],gs[N][M][M];
int add(int x,int y){
x+=y;
return (x<mod ? x : x-mod);
}
struct Data{
int f,g,g0,g1;
Data upd0(int x){
return Data{f,(int)((g+(ll)x*g0)%mod),g0,add(f,g1)};
}
Data upd1(int x){
return Data{f,(int)((g+(ll)(m-x+1)*g1)%mod),add(f,g0),g1};
}
}fp[N][M][M];
Data add(Data x,Data y){
return Data{add(x.f,y.f),add(x.g,y.g),add(x.g0,y.g0),add(x.g1,y.g1)};
}
Data dec(Data x,Data y){
return Data{add(x.f,mod-y.f),add(x.g,mod-y.g),add(x.g0,mod-y.g0),add(x.g1,mod-y.g1)};
}
void get_sum(Data a[M][M]){
for(int i=0;i<=m;i++)
for(int j=m+1;j>i;j--){
if (i)a[i][j]=add(a[i][j],a[i-1][j]);
if (j<=m)a[i][j]=add(a[i][j],a[i][j+1]);
if ((i)&&(j<=m))a[i][j]=dec(a[i][j],a[i-1][j+1]);
}
}
void get_fp(){
memset(fp,0,sizeof(fp));
for(int x=0;x<=m;x++)
for(int y=x+1;y<=m+1;y++)fp[0][x][y]=Data{1,0,0,0};
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if ((i<=n0)&&(a[i]!=j))continue;
for(int x=0;x<j;x++){
fp[i][x][j]=add(fp[i][x][j],fp[i-1][x][j+1].upd0(j));
if (x)fp[i][x][j]=dec(fp[i][x][j],fp[i-1][x-1][j+1].upd0(j));
}
for(int y=j+1;y<=m+1;y++){
fp[i][j][y]=add(fp[i][j][y],fp[i-1][j-1][y].upd1(j));
if (y<=m)fp[i][j][y]=dec(fp[i][j][y],fp[i-1][j-1][y+1].upd1(j));
}
}
get_sum(fp[i]);
}
}
void get_sum(int a[M][M]){
for(int i=0;i<=m;i++)
for(int j=m+1;j>i;j--){
if (i)a[i][j]=add(a[i][j],a[i-1][j]);
if (j<=m)a[i][j]=add(a[i][j],a[i][j+1]);
if ((i)&&(j<=m))a[i][j]=add(a[i][j],mod-a[i-1][j+1]);
}
}
void get_fs(){
memset(fs,0,sizeof(fs));
for(int x=0;x<=m;x++)
for(int y=x+1;y<=m+1;y++)fs[n+1][x][y]=1;
for(int i=n;i;i--){
for(int j=1;j<=m;j++){
if ((i<=n0)&&(a[i]!=j))continue;
for(int x=0;x<j;x++){
fs[i][x][j]=add(fs[i][x][j],fs[i+1][x][j+1]);
if (x)fs[i][x][j]=add(fs[i][x][j],mod-fs[i+1][x-1][j+1]);
}
for(int y=j+1;y<=m+1;y++){
fs[i][j][y]=add(fs[i][j][y],fs[i+1][j-1][y]);
if (y<=m)fs[i][j][y]=add(fs[i][j][y],mod-fs[i+1][j-1][y+1]);
}
}
get_sum(fs[i]);
}
}
void get_Fp(){
memset(Fp,0,sizeof(Fp));
for(int x=0;x<=m;x++)
for(int y=x+1;y<=m+1;y++)Fp[0][0][x][y]=1;
for(int i=1;i<=n;i++)
for(int z=0;z<=i;z++){
for(int j=1;j<=m;j++){
if ((i<=n0)&&(a[i]!=j))continue;
for(int x=0;x<j;x++){
Fp[i][z][x][j]=add(Fp[i][z][x][j],Fp[i-1][z][x][j+1]);
if (x)Fp[i][z][x][j]=add(Fp[i][z][x][j],mod-Fp[i-1][z][x-1][j+1]);
}
if (z){
for(int y=j+1;y<=m+1;y++){
Fp[i][z][j][y]=add(Fp[i][z][j][y],Fp[i-1][z-1][j-1][y]);
if (y<=m)Fp[i][z][j][y]=add(Fp[i][z][j][y],mod-Fp[i-1][z-1][j-1][y+1]);
}
}
}
get_sum(Fp[i][z]);
}
}
void get_gp(int w){
memset(gp0,0,sizeof(gp0));
memset(gp1,0,sizeof(gp1));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if ((i<=n0)&&(a[i]!=j))continue;
for(int x=0;x<j;x++){
gp0[i][x][j]=add(gp0[i][x][j],gp0[i-1][x][j+1]);
gp1[i][x][j]=add(gp1[i][x][j],gp1[i-1][x][j+1]);
if (x){
gp0[i][x][j]=add(gp0[i][x][j],mod-gp0[i-1][x-1][j+1]);
gp1[i][x][j]=add(gp1[i][x][j],mod-gp1[i-1][x-1][j+1]);
}
}
for(int y=j+1;y<=m+1;y++){
gp0[i][j][y]=add(gp0[i][j][y],gp0[i-1][j-1][y]);
gp1[i][j][y]=add(gp1[i][j][y],gp1[i-1][j-1][y]);
if (y<=m){
gp0[i][j][y]=add(gp0[i][j][y],mod-gp0[i-1][j-1][y+1]);
gp1[i][j][y]=add(gp1[i][j][y],mod-gp1[i-1][j-1][y+1]);
}
}
if (j<w){
for(int x=0;x<j;x++){
gp0[i][x][j]=(gp0[i][x][j]+(ll)w*fp[i-1][x][j+1].f)%mod;
if (x)gp0[i][x][j]=(gp0[i][x][j]+(ll)w*(mod-fp[i-1][x-1][j+1].f))%mod;
}
for(int y=j+1;y<=m+1;y++){
gp0[i][j][y]=(gp0[i][j][y]+(ll)w*fp[i-1][j-1][y].f)%mod;
if (y<=m)gp0[i][j][y]=(gp0[i][j][y]+(ll)w*(mod-fp[i-1][j-1][y+1].f))%mod;
}
}
if (j>w){
for(int x=0;x<j;x++){
gp1[i][x][j]=(gp1[i][x][j]+(ll)(m-w+1)*fp[i-1][x][j+1].f)%mod;
if (x)gp1[i][x][j]=(gp1[i][x][j]+(ll)(m-w+1)*(mod-fp[i-1][x-1][j+1].f))%mod;
}
for(int y=j+1;y<=m+1;y++){
gp1[i][j][y]=(gp1[i][j][y]+(ll)(m-w+1)*fp[i-1][j-1][y].f)%mod;
if (y<=m)gp1[i][j][y]=(gp1[i][j][y]+(ll)(m-w+1)*(mod-fp[i-1][j-1][y+1].f))%mod;
}
}
}
get_sum(gp0[i]),get_sum(gp1[i]);
}
}
void get_gs(int w){
memset(gs,0,sizeof(gs));
for(int i=n;i;i--){
for(int j=1;j<=m;j++){
if ((i<=n0)&&(a[i]!=j))continue;
for(int x=0;x<j;x++){
gs[i][x][j]=add(gs[i][x][j],gs[i+1][x][j+1]);
if (x)gs[i][x][j]=add(gs[i][x][j],mod-gs[i+1][x-1][j+1]);
}
for(int y=j+1;y<=m+1;y++){
gs[i][j][y]=add(gs[i][j][y],gs[i+1][j-1][y]);
if (y<=m)gs[i][j][y]=add(gs[i][j][y],mod-gs[i+1][j-1][y+1]);
}
if (j==w){
for(int x=0;x<j;x++){
gs[i][x][j]=add(gs[i][x][j],fs[i+1][x][j+1]);
if (x)gs[i][x][j]=add(gs[i][x][j],mod-fs[i+1][x-1][j+1]);
}
for(int y=j+1;y<=m+1;y++){
gs[i][j][y]=add(gs[i][j][y],fs[i+1][j-1][y]);
if (y<=m)gs[i][j][y]=add(gs[i][j][y],mod-fs[i+1][j-1][y+1]);
}
}
}
get_sum(gs[i]);
}
}
int main(){
scanf("%d",&t);
while (t--){
scanf("%d%d%d",&n,&m,&n0);
for(int i=1;i<=n0;i++)scanf("%d",&a[i]);
ans1=ans2=0;
get_fp(),get_fs(),get_Fp();
for(int i=1;i<n;i++)
for(int j=1;j<=m;j++){
if ((i<=n0)&&(a[i]!=j)||(i<n0)&&(a[i+1]!=j))continue;
int s=fs[i+2][j-1][j+1];
ans1=(ans1+(ll)fp[i-1][j-1][j+1].f*s)%mod;
ans2=(ans2+(ll)fp[i-1][j-1][j+1].g*s)%mod;
for(int z=0;z<i;z++)ans2=(ans2+(ll)(z*j+(i-z-1)*(m-j+1))*Fp[i-1][z][j-1][j+1]%mod*s)%mod;
}
for(int i=1;i<=m;i++){
if ((n<=n0)&&(a[n]!=i))continue;
ans1=add(ans1,fp[n-1][i-1][i+1].f);
ans2=add(ans2,fp[n-1][i-1][i+1].g);
for(int z=0;z<n;z++)ans2=(ans2+(ll)max(z*i,(n-z-1)*(m-i+1))*Fp[n-1][z][i-1][i+1])%mod;
}
for(int i=1;i<n;i++)
for(int x=1;x<=m;x++){
if ((i<=n0)&&(a[i]!=x))continue;
for(int y=1;y<=m;y++){
if ((i<n0)&&(a[i+1]!=y))continue;
if (y<x){
int s=fs[i+2][y-1][x+1];
Data o=dec(fp[i-1][x-1][x+1],fp[i-1][y-1][x+1]);
ans1=(ans1+(ll)o.f*s)%mod,ans2=(ans2+(ll)o.g*s)%mod;
for(int z=0;z<i;z++)ans2=(ans2+(ll)max(z*x,(i-z-1)*(m-x+1))*(Fp[i-1][z][x-1][x+1]+mod-Fp[i-1][z][y-1][x+1])%mod*s)%mod;
}
if (y>x){
int s=fs[i+2][x-1][y+1];
Data o=dec(fp[i-1][x-1][x+1],fp[i-1][x-1][y+1]);
ans1=(ans1+(ll)o.f*s)%mod,ans2=(ans2+(ll)o.g*s)%mod;
for(int z=0;z<i;z++)ans2=(ans2+(ll)max(z*x,(i-z-1)*(m-x+1))*(Fp[i-1][z][x-1][x+1]+mod-Fp[i-1][z][x-1][y+1])%mod*s)%mod;
}
}
}
for(int w=1;w<=n;w++){
get_gp(w),get_gs(w);
for(int i=1;i<n;i++)
for(int j=1;j<=m;j++){
if ((i<=n0)&&(a[i]!=j)||(i<n0)&&(a[i+1]!=j))continue;
ans2=(ans2+(ll)(w<j ? (ll)gp0[i-1][j-1][j+1] : gp1[i-1][j-1][j+1])*gs[i+2][j-1][j+1])%mod;
}
for(int i=1;i<n;i++)
for(int x=1;x<=m;x++){
if ((i<=n0)&&(a[i]!=x))continue;
for(int y=1;y<=m;y++){
if ((i<n0)&&(a[i+1]!=y))continue;
if (y<x){
int g0=add(gp0[i-1][x-1][x+1],mod-gp0[i-1][y-1][x+1]);
int g1=add(gp1[i-1][x-1][x+1],mod-gp1[i-1][y-1][x+1]);
ans2=(ans2+(ll)(w<x ? g0 : g1)*(gs[i+2][y-1][x+1]+(y==w ? fs[i+2][y-1][x+1] : 0)))%mod;
}
if (y>x){
int g0=add(gp0[i-1][x-1][x+1],mod-gp0[i-1][x-1][y+1]);
int g1=add(gp1[i-1][x-1][x+1],mod-gp1[i-1][x-1][y+1]);
ans2=(ans2+(ll)(w<x ? g0 : g1)*(gs[i+2][x-1][y+1]+(y==w ? fs[i+2][x-1][y+1] : 0)))%mod;
}
}
}
}
printf("%d %d\n",ans1,ans2);
}
return 0;
}