#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define p_b push_back using namespace std; typedef long long ll; const int mod=147744151; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m; inline int add(int a,int b){if((a+=b)>=mod)a-=mod;return a;} struct vec{ int a[6]; vec(){memset(a,0,sizeof(a));} }; struct mat{ int a[6][6]; mat(){memset(a,0,sizeof(a));} void init(){up(i,0,5)up(j,0,5)a[i][j]=(i==j);} }pw[2][2][2][3][1005]; //first:[mx<=i+1] [mx<=i+2] second:tot>=cnt+1-[p[i]=-1] mat operator*(mat a,mat b){ mat c; up(i,0,5)up(j,0,5)up(k,0,5)c.a[i][k]=(c.a[i][k]+a.a[i][j]*1ll*b.a[j][k])%mod; return c; } unsigned long long sum[6]; vec operator*(vec a,mat b){ vec c;up(i,0,5)sum[i]=0; up(i,0,5)up(j,0,5)sum[j]+=a.a[i]*1llu*b.a[i][j]; up(i,0,5)c.a[i]=sum[i]%mod; return c; } vec qr(vec a,int o1,int o2,int o3,int b){ a=a*pw[o1][o2][o3][0][b%1000];b/=1000; a=a*pw[o1][o2][o3][1][b%1000];b/=1000; a=a*pw[o1][o2][o3][2][b]; return a; } void slv(){ n=read(),m=read(); map<int,int>p,vis;bool ok=1; set<pi>_sp,_svis,_vismx; set<int>sp; while(m--){ ll u=read(); int x=(u-1)/n+1,y=(u-1)%n+1; up(i,x-3,x+3)if(i>1&&i<=n)sp.insert(i); up(i,y-3,y+3)if(i>1&&i<=n)sp.insert(i); if(p.count(x)){ if(p[x]!=y)ok=0; else continue; } if(vis[y])ok=0; else p[x]=y,vis[y]=x; } if(!ok)return puts("0"),void(); int cnt=0; for(auto it:p)cnt++,_sp.insert({it.p1,cnt}); cnt=0; for(auto it:vis)cnt++,_svis.insert({it.p1,cnt}); cnt=0; for(auto it:vis)cnt=max(cnt,it.p2),_vismx.insert({it.p1,cnt}); auto qs_not=[&](int k){ auto it=_sp.lower_bound({k,0}); if(it==_sp.end())return (int)_sp.size(); if((*it).p1==k)return (*it).p2; return (*it).p2-1; }; auto qs=[&](int k){return k-qs_not(k);}; auto qvis_not=[&](int k){ auto it=_svis.lower_bound({k,0}); if(it==_svis.end())return (int)_svis.size(); if((*it).p1==k)return (*it).p2; return (*it).p2-1; }; auto qvis=[&](int k){return k-qvis_not(k);}; auto qpre=[&](int k){ if(_vismx.empty())return -1; auto it=_vismx.lower_bound({k,0}); if(it==_vismx.end())return (*(--it)).p2; if((*it).p1==k)return (*it).p2; if(it==_vismx.begin())return -1; return (*(--it)).p2; }; auto chk=[&](int x,int y){ if(y>n)return 0; if(p.count(x))return p[x]==y?1:0; if(!vis[y])return 1; return 0; }; auto ZY=[&](int _i,vec a){ vec b;up(i,2,5)b.a[i-2]=a.a[i]; up(i,_i-3,_i-1)if(i>=1){ int w0=a.a[4-(_i-1-i)*2],w1=a.a[5-(_i-1-i)*2]; int s=add(w0,w1),mx=qpre(i),tot=qvis(i),cnt=qs(i); if(chk(i,i)&&i+1==_i)b.a[5]=add(b.a[5],w1); if(chk(i,i+1)&&mx<=i+1&&((p.count(i+1)&&p[i+1]<=i)||((!p.count(i+1))&&tot>=cnt+1-(!p.count(i)))))if(i+2==_i)b.a[5]=add(b.a[5],s); if(chk(i,i+1)&&i+1==_i)b.a[4]=add(b.a[4],s); if(chk(i,i+2)&&chk(i+2,i+1)&&((p.count(i+1)&&p[i+1]<=i)||(!p.count(i+1)))&&mx<=i+2&&i+3==_i)b.a[5]=add(b.a[5],s); if(chk(i,i+2)&&((p.count(i+1)&&p[i+1]<=i)||((!p.count(i+1))&&tot>=cnt+1-(!p.count(i)))))if(i+2==_i)b.a[4]=add(b.a[4],s); } return b; }; vec a;up(i,0,5)a.a[i]=(i==5); int lst=2; sp.insert(n+1); for(int x:sp){ if(lst<x){ int tot=qvis(lst),cnt=qs(lst); int o1=qpre(lst)<=lst+1,o2=qpre(lst)<=lst+2,o3=tot>=cnt+1-(!p.count(lst)); a=qr(a,o1,o2,o3,x-lst); } lst=x+1,a=ZY(x,a); } printf("%d\n",a.a[5]); } void init(){ up(_,0,1)up(__,0,1)up(___,0,1){ mat x; up(i,2,5)x.a[i][i-2]=1; x.a[5][5]=1; if(_&&___)x.a[3][5]=x.a[2][5]=1; x.a[5][4]=x.a[4][4]=1; if(__)x.a[0][5]=x.a[1][5]=1; if(___)x.a[2][4]=x.a[3][4]=1; up(i,0,2){ mat y=(!i)?x:pw[_][__][___][i-1][1000]; pw[_][__][___][i][0].init(); up(k,1,1000)pw[_][__][___][i][k]=pw[_][__][___][i][k-1]*y; } } } int main(){ //freopen("party.in","r",stdin),freopen("party.out","w",stdout); init();int t=read();while(t--)slv(); return 0; }