发现每次对行的操作相当于将这一行的元素复合上一个排列，对列也同理。不妨记这两个排列为 \(p,q\)。
首先考虑一个弱化版：如果 \(p,q\) 都是一个环怎么处理。如果 \(n=1\) 那么答案显然是 \(a\) 的最小周期，使用 KMP 求解。对于 \(m=1\) 的情况也同理。考虑 \(n,m\ge 2\)，发现我们可以在不影响其他元素的情况下对如下图所示的三个元素做以下置换：
如果我们把整个矩阵从上到下，从左到右拼接形成一个序列，那么容易发现该操作不影响该序列逆序对数的奇偶性。而从另一个角度来说，如果一个矩阵组成元素和原矩阵相同，逆序对个数的奇偶性也与原矩阵相同，那么其就可以通过进行若干次操作获得，方法就是逐格还原。因此如果矩阵中存在相同的数，答案就是由这些元素组成的可能的矩阵个数，即 \(\dfrac{(nm)!}{\prod cnt_i!}\)。否则，我们发现，如果 \(m\) 是偶数，那么我们对任意一行进行操作以后，矩阵逆序对个数的奇偶性就会改变，因此如果 \(n,m\) 之一为偶数，那么对于那些逆序对个数奇偶性与原矩阵不同的矩阵，则可以通过对行 / 列的单次操作后通过上述针对三个元素的操作得到，答案就是 \((nm)!\)。否则无论如何矩阵的奇偶性都无法改变。
接下来考虑原问题，显然，一个位置 \((x,y)\) 上的元素可能到达 \((x',y')\)，当且仅当 \(x,x'\) 在 \(p\) 的同一置换环内，\(y,y'\) 在 \(q\) 的同一置换环内，我们不妨将互相可达的位置称作一个“等价类”，依次考虑每个等价类，分情况讨论：
- 如果这个等价类的长为 \(1\)，或宽为 \(1\)，求其最小周期，然后求 LCM，具体细节见代码。
- 如果这个等价类的长宽都大于 \(1\)，且有重复元素，则此等价类对答案的贡献为 \(\dfrac{(NM)!}{\prod cnt_i!}\)，其中 \(N,M\) 为这个等价类的长和宽。
- 如果这个等价类的长宽都大于 \(1\)，且没有重复元素，那么不管怎么样我们都先给答案乘个 \(\dfrac{(NM)!}{2}\) 再说，剩下 \(2\) 的系数留给决定每个等价类的奇偶性，这里我们继续分情况讨论：
- 如果这个等价类长宽都是奇数，那么不论怎样该等价类的奇偶性都不会改变，没有贡献系数。
- 如果这个等价类长宽中恰有一者是奇数，不妨假设宽是奇数，那么我们只能通过操纵行所在的置换环对应的列来改变该等价类的奇偶性，一旦行所在置换环中所有列操作次数总数确定，那么该等价类的奇偶性就确定了，因此考虑维护一个集合 \(S\)，每次遇到一个这样的置换环，就将其行所在置换环的编号加入 \(S\)，最后总贡献系数就是 \(2^{|S|}\)。
- 如果这个等价类长宽都是偶数，同理，如果其行、列所在置换环的操作次数都确定了，那么该等价类的奇偶性也确定了。因此考虑维护一个集合 \(T\)，每次遇到这样的置换环就将其行列所在置换环编号加入 \(T\)，总贡献 \(2^{|T|}\)。
总之细节很多很烦。
const int MAXN=3e6;
const int MAXV=3e6;
const int MOD=998244353;
const int INV2=MOD+1>>1;
int qpow(int x,int e){
int ret=1;
for(;e;e>>=1,x=1ll*x*x%MOD)if(e&1)ret=1ll*ret*x%MOD;
return ret;
}
int n,m,fac[MAXN+5],ifac[MAXN+5];
int getid(int x,int y){return (x-1)*m+y;}
int pr[MAXN+5],mnp[MAXN+5],prcnt=0;
void sieve(int n){
for(int i=2;i<=n;i++){
if(!mnp[i])pr[++prcnt]=i,mnp[i]=i;
for(int j=1;j<=prcnt&&pr[j]*i<=n;j++){
mnp[pr[j]*i]=pr[j];
if(i%pr[j]==0)break;
}
}
}
void init_fac(int n){
for(int i=(fac[0]=ifac[0]=ifac[1]=1)+1;i<=n;i++)
ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=1;i<=n;i++){
fac[i]=1ll*fac[i-1]*i%MOD;
ifac[i]=1ll*ifac[i-1]*ifac[i]%MOD;
}
}
int a[MAXN+5],vis[MAXN+5];
int p[MAXN+5],lp,q[MAXN+5],lq;
int idp[MAXN+5],idp_cnt,lenp[MAXN+5];
int idq[MAXN+5],idq_cnt,lenq[MAXN+5];
int cnt[MAXV+5];
int f[MAXN*2+5],siz[MAXN*2+5];
int find(int x){return (!f[x])?x:f[x]=find(f[x]);}
void merge(int x,int y){
x=find(x);y=find(y);
if(x!=y)f[x]=y,siz[y]+=siz[x];
}
void clear(){
lp=lq=0;
for(int i=1;i<=n;i++)idp[i]=lenp[i]=0;idp_cnt=0;
for(int i=1;i<=m;i++)idq[i]=lenq[i]=0;idq_cnt=0;
for(int i=1;i<=n+m;i++)f[i]=0;
}
int calc(vector<int>v){
int N=v.size();v.insert(v.begin(),0);
vector<int>fail(N+1);
for(int i=2,j=0;i<=N;i++){
while(j&&v[j+1]!=v[i])j=fail[j];
if(v[j+1]==v[i])++j;
fail[i]=j;
}
int res=N;
for(int i=fail[N];i;i=fail[i])if(N%(N-i)==0)chkmin(res,N-i);
return res;
}
void solve(){
read(n);read(m);clear();
for(int i=1;i<=n*m;i++)read(a[i]),vis[i]=0;
for(int i=1;i<=n;i+=2)p[++lp]=i;
for(int i=2;i<=n;i+=2)p[++lp]=i;
for(int i=1;i<=m;i+=2)q[++lq]=i;
for(int i=2;i<=m;i+=2)q[++lq]=i;
for(int i=1;i<=n;i++)if(!idp[i]){
++idp_cnt;
for(int j=i;!idp[j];j=p[j])idp[j]=idp_cnt,lenp[idp_cnt]++;
}
for(int i=1;i<=m;i++)if(!idq[i]){
++idq_cnt;
for(int j=i;!idq[j];j=q[j])idq[j]=idq_cnt,lenq[idq_cnt]++;
}
for(int i=1;i<=idp_cnt+idq_cnt;i++)siz[i]=1;
int prd=1;
map<int,int>A,B,C,D;
for(int i=1;i<=n;i++)if(p[i]!=i)for(int j=1;j<=m;j++)if(q[j]!=j){
if(vis[getid(i,j)])continue;
vector<int>X,Y,vec;
int tmp=i;do{X.pb(tmp);tmp=p[tmp];}while(tmp!=i);
tmp=j;do{Y.pb(tmp);tmp=q[tmp];}while(tmp!=j);
for(int x:X)for(int y:Y){
vis[getid(x,y)]=1;cnt[a[getid(x,y)]]++;
if(cnt[a[getid(x,y)]]==1)vec.pb(a[getid(x,y)]);
}
int P=idp[i],Q=idq[j];
if(vec.size()!=lenp[P]*lenq[Q]){
prd=1ll*prd*fac[lenp[P]*lenq[Q]]%MOD;
for(int x:vec)prd=1ll*prd*ifac[cnt[x]]%MOD;
}else{
prd=1ll*prd*fac[lenp[P]*lenq[Q]]%MOD*INV2%MOD;
if(lenp[P]%2==1&&lenq[Q]%2==0)A[P]=1;
else if(lenp[P]%2==0&&lenq[Q]%2==1)B[Q]=1;
else if(lenp[P]%2==0&&lenq[Q]%2==0)C[P]=D[Q]=1,merge(P,Q+idp_cnt);
}
for(int x:vec)cnt[x]=0;
}
prd=1ll*prd*qpow(2,A.size()+B.size()+C.size()+D.size())%MOD;
for(int i=1;i<=idp_cnt+idq_cnt;i++)if(find(i)==i&&siz[i]>1)
prd=1ll*prd*INV2%MOD;
for(int i=1;i<=n;i++)if(p[i]==i){
static bool used[MAXN+5];static int mx[MAXN+5];
for(int j=1;j<=m;j++)used[j]=mx[j]=0;
for(int j=1;j<=m;j++)if(!used[j]){
vector<int>v;
for(int k=j;!used[k];k=q[k])used[k]=1,v.pb(a[getid(i,k)]);
int len=calc(v);
while(len^1){
int p=mnp[len],cnt=0;
while(len%p==0)cnt++,len/=p;
chkmax(mx[p],cnt);
}
}
for(int j=1;j<=m;j++)if(mx[j])prd=1ll*prd*qpow(j,mx[j])%MOD;
}
for(int i=1;i<=m;i++)if(q[i]==i){
static bool used[MAXN+5];static int mx[MAXN+5];
for(int j=1;j<=n;j++)used[j]=mx[j]=0;
for(int j=1;j<=n;j++)if(!used[j]){
vector<int>v;
for(int k=j;!used[k];k=p[k])used[k]=1,v.pb(a[getid(k,i)]);
int len=calc(v);
while(len^1){
int p=mnp[len],cnt=0;
while(len%p==0)cnt++,len/=p;
chkmax(mx[p],cnt);
}
}
for(int j=1;j<=n;j++)if(mx[j])prd=1ll*prd*qpow(j,mx[j])%MOD;
}
printf("%d\n",prd);
}