#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define fi first #define se second const int N = 1e4 + 5; const int mod = 147744151; int T, n, m; int a[N], b[N]; void add(int &x, int y) { x += y; if (x >= mod) x -= mod; } struct mat { int m[2][2]; mat() { memset(m, 0, sizeof(m)); } } F, G; mat operator * (const mat &a, const mat &b) { mat c; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) add(c.m[i][k], a.m[i][j] * b.m[j][k] % mod); return c; } void solve() { cin >> n >> m; int tag = 1; map<int, int> mp, mp2; vector<int> v; v.push_back(1), v.push_back(n + 1); for (int i = 1, t, x, y; i <= m; i++) { cin >> t; x = (t - 1) / n + 1, y = (t - 1) % n + 1; if (mp.count(x) && mp[x] != y) tag = 0; if (!mp.count(x) && mp2.count(y)) tag = 0; if (y > x + 2) tag = 0; mp[x] = y, mp2[y] = 1; a[i] = x, b[i] = y; for (int j = -2; j <= 2; j++) { if (x + j > 0 && x + j <= n) v.push_back(x + j); if (y + j > 0 && y + j <= n) v.push_back(y + j); } } if (!tag) { cout << "0\n"; return; } sort(a + 1, a + m + 1); int ma = unique(a + 1, a + m + 1) - a - 1; sort(b + 1, b + m + 1); int mb = unique(b + 1, b + m + 1) - b - 1; v.push_back(n - 1), v.push_back(n); sort(v.begin(), v.end()); int sz = unique(v.begin(), v.end()) - v.begin(); F.m[0][0] = 1; for (int i = 0; i < sz - 1; i++) { int j = v[i]; memset(G.m, 0, sizeof(G.m)); if (mp.count(j)) { if (mp[j] == j + 2) G.m[0][1] = 1; else { G.m[0][0] = 1; if (mp[j] != j) G.m[1][0] = 1; } } else { if (j + 2 <= n && !mp2.count(j + 2)) G.m[0][1] = 1; int t1 = upper_bound(a + 1, a + ma + 1, j - 1) - a - 1; int t2 = upper_bound(b + 1, b + mb + 1, j + 1) - b - 1; if (t2 == t1) { if (j + 1 <= n) G.m[0][0] = 2; else G.m[0][0] = 1; } else if (t2 - t1 == 1) G.m[0][0] = 1; t1 = upper_bound(a + 1, a + ma + 1, j - 2) - a - 1; t2 = upper_bound(b + 1, b + mb + 1, j - 1) - b - 1; if (t2 == t1) G.m[1][0] = 1; } int t = v[i + 1] - v[i]; while (t) { if (t & 1) F = F * G; t >>= 1; G = G * G; } } cout << F.m[0][0] << '\n'; } signed main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> T; while (T--) solve(); return 0; }