#include<bits/stdc++.h> using namespace std; #define int long long #define lson (pos<<1) #define rson (pos<<1|1) #define ll long long #define pii pair<int,int> #define pil pair<int,ll> #define fr first #define sc second #define mk make_pair #define pb push_back ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;} bool AAA; const int MAXN=200010,N=20,Mod=147744151; int n,m,op,ans,a[MAXN]; struct matrix{ int p[2][2]; matrix operator*(const matrix&G)const{ matrix res; res.p[0][0]=(p[0][0]*G.p[0][0]+p[0][1]*G.p[1][0])%Mod; res.p[0][1]=(p[0][0]*G.p[0][1]+p[0][1]*G.p[1][1])%Mod; res.p[1][0]=(p[1][0]*G.p[0][0]+p[1][1]*G.p[1][0])%Mod; res.p[1][1]=(p[1][0]*G.p[0][1]+p[1][1]*G.p[1][1])%Mod; return res; } void prt(){ cout<<p[0][0]<<" "<<p[0][1]<<endl; cout<<p[1][0]<<" "<<p[1][1]<<endl; } }P,A; map<int,int>mp; set<int>st; int p[MAXN],k; int ap[MAXN],bp[MAXN]; void slv(){ k=0,mp.clear(),st.clear(); n=read(),m=read(); for(int i=1;i<=m;i++)a[i]=read(); sort(a+1,a+m+1),m=unique(a+1,a+m+1)-a-1; p[++k]=1,p[++k]=n+1,p[++k]=n,p[++k]=n-1,mp[n+1]=n+1,st.insert(n+1); for(int i=1;i<=m;i++){ int x=(a[i]-1)/n+1,y=(a[i]-1)%n+1; if(mp[x]&&mp[x]!=y||y>x+2){puts("0");return;} mp[x]=y,st.insert(y); for(int j=x-2;j<=x+2;j++)if(1<=j&&j<=n)p[++k]=j; for(int j=y-2;j<=y+2;j++)if(1<=j&&j<=n)p[++k]=j; ap[i]=x,bp[i]=y; // cout<<x<<" "<<y<<endl; } m++;ap[m]=n+1,bp[m]=n+1; sort(ap+1,ap+m+1),sort(bp+1,bp+m+1); for(int i=1;i<=m;i++)if(ap[i]==ap[i-1]||bp[i]==bp[i-1]){puts("0");return;} sort(p+1,p+k+1),k=unique(p+1,p+k+1)-p-1; A.p[0][0]=A.p[0][1]=A.p[1][0]=A.p[1][1]=0; A.p[0][0]=1; // for(int i=1;i<=m;i++)cerr<<ap[i]<<" "<<bp[i]<<endl; for(int i=1;i<k;i++){ int x=p[i]; P.p[0][0]=P.p[0][1]=P.p[1][0]=P.p[1][1]=0; if(mp.count(x)){ if(mp[x]==x+2)P.p[0][1]=1; else P.p[0][0]=1,P.p[1][0]=mp[x]!=x; } else{ if(!st.count(x+2))P.p[0][1]=1; int ls=upper_bound(ap+1,ap+m+1,x)-ap-1,rs=upper_bound(bp+1,bp+m+1,x+1)-bp-1; if(rs==ls)P.p[0][0]=2; else if(rs==ls+1)P.p[0][0]=1; else P.p[0][0]=0; ls=upper_bound(ap+1,ap+m+1,x-2)-ap-1,rs=upper_bound(bp+1,bp+m+1,x-1)-bp-1; // cout<<" "<<ls<<" "<<rs<<endl; // for(int i=1;i<=ls;i++)cout<<ap[i]<<" ";cout<<';'; // for(int i=1;i<=rs;i++)cout<<bp[i]<<" ";cout<<endl; if(ls==rs)P.p[1][0]=1; } // cout<<x<<":"<<endl; // P.prt();cout<<endl; int t=p[i+1]-p[i]; while(t){ if(t&1)A=A*P; P=P*P,t>>=1; } // cout<<A.p[0][0]<<" "<<A.p[0][1]<<endl; } printf("%lld\n",A.p[0][0]); } signed main(){ //freopen("1.in","r",stdin);freopen("1.out","w",stdout); int _=read();while(_--) slv(); // cerr<<(clock()*1.0)/CLOCKS_PER_SEC<<"s\n"; return 0; }