#include #include #include using namespace std; using u64 = unsigned long long; using mint = atcoder::modint998244353; u64 pre_prod[256][256] = { 0 }; u64 pre_inv[256] = { 0 }; u64 nim_product(u64 a, u64 b, int d = 6) noexcept { if (min(a, b) <= 1) return a * b; if (a < 256 && b < 256 && pre_prod[a][b]) { return pre_prod[a][b]; } d--; u64 d_pow = 1ULL << d; u64 d_pow_pow = 1ULL << d_pow; if (a < d_pow_pow && b < d_pow_pow) { return nim_product(a, b, d); } u64 au = a >> d_pow; u64 al = a - (au << d_pow); u64 bu = b >> d_pow; u64 bl = b - (bu << d_pow); u64 aubu = nim_product(au, bu, d); u64 albu = nim_product(al, bu, d); u64 aubl = nim_product(au, bl, d); u64 albl = nim_product(al, bl, d); u64 res = ((aubu ^ aubl ^ albu) << d_pow) ^ (nim_product(aubu, d_pow_pow / 2, d)) ^ (albl); if (a < 256 && b < 256) pre_prod[a][b] = pre_prod[b][a] = res; return res; } u64 nim_product_inv(u64 a, int d = 6) { if (a < 256) return pre_inv[a]; d--; u64 d_pow = 1 << d; u64 au = a >> d_pow; u64 al = a - (au << d_pow); u64 half_inv = nim_product_inv(nim_product(au ^ al, al, d) ^ nim_product(nim_product(au, au, d), 1ULL << (d_pow - 1)), d); return (nim_product(half_inv, au, d) << d_pow) ^ nim_product(half_inv, au ^ al, d); } int main() { // precalc for (int a = 1; a < 256; a++) { for (int b = a; b < 256; b++) { u64 c = nim_product(a, b); if (c == 1) { pre_inv[a] = b; pre_inv[b] = a; } } } int n, t; cin >> n >> t; vector h(t, vector(n)); for (int r = 0; r < t; r++) { for (int c = 0; c < n; c++) { cin >> h[r][c]; h[r][c]--; } } // 通常の掃き出し(pop_backの都合上、右から) vector use(t, -1); for (int c0 = n - 1; c0 >= 0; c0--) { int r0 = -1; for (int r = 0; r < t; r++) { if (h[r][c0] == 0 || use[r] != -1) continue; use[r] = c0; r0 = r; break; } if (r0 == -1) continue; u64 inv = nim_product_inv(h[r0][c0]); for (auto& v : h[r0]) v = nim_product(v, inv); for (int r = 0; r < t; r++) { if (r == r0) continue; for (int c = 0; c < n; c++) { h[r][c] ^= nim_product(h[r0][c], h[r][c0]); } } } // 正方行列の生成 vector base_a(n, vector(n)); for (int i = 0; i < t; i++) { if (use[i] != -1) { base_a[use[i]] = h[i]; } } mint ans = 0; mint mul = mint(2).pow(64); auto dfs = [&](auto self, vector>& a, mint add, int pop, int column) -> void { if (column < 0) { ans += pop % 2 ? -add : add; return; } // この列を消さない auto a0 = a; mint add0 = add; if (a0.back().back() == 0) add0 *= mul; a0.pop_back(); for (auto& r : a0) r.pop_back(); self(self, a0, add0, pop, column - 1); // この列を消す auto a1 = a; for (auto& r : a1) r.pop_back(); // 別の列の要素があるなら、そこを掃き出す(O(column^2)) for (int c0 = a1.back().size() - 1; c0 >= 0; c0--) { if (a1.back()[c0]) { u64 ainv = nim_product_inv(a1.back()[c0]); for (auto& v : a1.back()) v = nim_product(v, ainv); for (int r = 0; r < a1.size(); r++) { for (int c = 0; c < a1[r].size(); c++) { if (r == c0) { if (a1[r][c0] != a1.back()[c0]) a1[r][c] ^= a1.back()[c]; } else { a1[r][c] ^= nim_product(a1.back()[c], a1[r][c0]); } } } break; } } a1.pop_back(); self(self, a1, add, pop + 1, column - 1); return; }; dfs(dfs, base_a, 1, 0, n - 1); cout << ans.val() << endl; }