#include using namespace std; #define overload2(a, b, c, ...) c #define overload3(a, b, c, d, ...) d #define overload4(a, b, c, d, e ...) e #define overload5(a, b, c, d, e, f ...) f #define overload6(a, b, c, d, e, f, g ...) g #define fast_io ios::sync_with_stdio(false); cin.tie(nullptr); #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") typedef long long ll; typedef long double ld; #define chmin(a,b) a = min(a,b); #define chmax(a,b) a = max(a,b); #define bit_count(x) __builtin_popcountll(x) #define leading_zero_count(x) __builtin_clz(x) #define trailing_zero_count(x) __builtin_ctz(x) #define gcd(a,b) __gcd(a,b) #define lcm(a,b) a / gcd(a,b) * b #define rep(...) overload3(__VA_ARGS__, rrep, rep1)(__VA_ARGS__) #define rep1(i,n) for(int i = 0 ; i < n ; i++) #define rrep(i,a,b) for(int i = a ; i < b ; i++) #define repi(it,S) for(auto it = S.begin() ; it != S.end() ; it++) #define pt(a) cout << a << endl; #define print(...) printall(__VA_ARGS__); #define debug(a) cout << #a << " " << a << endl; #define all(a) a.begin(), a.end() #define endl "\n"; #define v1(T,n,a) vector(n,a) #define v2(T,n,m,a) vector>(n,v1(T,m,a)) #define v3(T,n,m,k,a) vector>>(n,v2(T,m,k,a)) #define v4(T,n,m,k,l,a) vector>>>(n,v3(T,m,k,l,a)) templateistream &operator>>(istream&is,pair&p){is>>p.first>>p.second;return is;} templateostream &operator<<(ostream&os,const pair&p){os<istream &operator>>(istream&is,vector&v){for(T &in:v){is>>in;}return is;} templateostream &operator<<(ostream&os,const vector&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;} templateistream &operator>>(istream&is,vector>&v){for(T &in:v){is>>in;}return is;} templateostream &operator<<(ostream&os,const vector>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?"\n":"");}return os;} templateostream &operator<<(ostream&os,const set&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;} templateostream &operator<<(ostream&os,const multiset&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;} template void printall(Args... args){for(auto i:initializer_list>{args...}) cout< struct BitMatrix{ private: int row, col; vector> mat; void init_(vector> A){ row = A.size(); col = A[0].size(); mat.resize(row); for(int i = 0; i < row; i++){ for(int j = 0; j < col; j++){ if(A[i][j] != 0) mat[i][j] = 1; else mat[i][j] = 0; } } } void init_(vector A, bool row_matrix = false){ if(row_matrix) { col = (int)A.size(); row = 1; mat.resize(1); for(int i = 0; i < col; i++){ if(A[i] != 0) mat[0][i] = 1; else mat[0][i] = 0; } } else { col = 1; row = (int)A.size(); mat.resize(row); for(int i = 0; i < row; i++){ if(A[i] != 0) mat[i][0] = 1; else mat[i][0] = 0; } } } void transpose_() { vector> res(col); rep(i,row) rep(j,col) res[j][i] = mat[i][j]; mat = res; swap(row,col); } void flip_() { rep(i,row) rep(j,col) mat[i][j].flip(); } void concat_col_(vector &Y) { BitMatrix X(Y); concat_col_(X); } void concat_col_(vector> &Y) { BitMatrix X(Y); concat_col_(X); } void concat_col_(BitMatrix &Y) { assert((int)Y.row == row); rep(i,row) { rep(j,Y.col) mat[i][j+col] = (Y.mat[i][j]); } col += Y.col; } void concat_row_(vector &Y) { BitMatrix X(Y,true); concat_row_(X); } void concat_row_(vector> &Y) { BitMatrix X(Y); concat_row_(X); } void concat_row_(BitMatrix &Y) { assert((int)Y.col == col); row += Y.row; rep(i,Y.row) mat.push_back(Y.mat[i]); } void print_() { rep(i,row){ rep(j,col) cout << mat[i][j]; cout << endl; } } public: inline BitMatrix &operator&=(const BitMatrix Y) { rep(i,row) mat[i] &= Y.mat[i]; return *this ; } inline BitMatrix &operator|=(const BitMatrix Y) { rep(i,row) mat[i] |= Y.mat[i]; return *this ; } inline BitMatrix &operator^=(const BitMatrix Y) { rep(i,row) mat[i] ^= Y.mat[i]; return *this ; } inline BitMatrix operator&(const BitMatrix Y) const { return BitMatrix(*this) &= Y; } inline BitMatrix operator|(const BitMatrix Y) const { return BitMatrix(*this) |= Y; } inline BitMatrix operator^(const BitMatrix Y) const { return BitMatrix(*this) += Y; } inline bool operator==(const BitMatrix Y) const { return mat == Y.mat; } inline bool operator!=(const BitMatrix Y) const { return mat != Y.mat; } inline bitset&operator[] (int i) {return mat[i]; } BitMatrix(int n): row(n), col(0) { mat.resize(row); } BitMatrix(vector A, bool row_matrix = false) { init_(A, row_matrix); } BitMatrix(vector> A){ init_(A); } void init(vector A, bool row_matrix = false) { init_(A, row_matrix); } void init(vector> A) { init_(A); } size_t row_size() { return row; } size_t col_size() { return col; } void transpose() { transpose_(); } void flip() { flip_(); } void concat_col(vector> &Y) { concat_col_(Y); } void concat_col(vector &Y) { concat_col_(Y); } void concat_col(BitMatrix &Y) { concat_col_(Y); } void concat_row(vector> &Y) { concat_row_(Y); } void concat_row(vector &Y) { concat_row_(Y); } void concat_row(BitMatrix &Y) { concat_row_(Y); } }; const int MAX_COL = 2520; using Matrix = BitMatrix; template struct GaussJordan{ private: int rank; vector solution; int sweep_out_(Matrix &A , bool is_extended = false){ rank = 0 ; for(int col = 0 ; col < A.col_size() ; col++){ if(is_extended && col == A.col_size() - 1) break ; int pivot = -1 ; for(int row = rank ; row < A.row_size() ; row++){ if(A[row][col]){ pivot = row ; break ; } } if(pivot == -1) continue ; swap(A[pivot] , A[rank]) ; for(int row = 0 ; row < A.row_size() ; row++){ if(row != rank && A[row][col]) A[row] ^= A[rank] ; } rank++ ; } return rank ; } vector> create_xorbase_(Matrix &A, bool sorted = false){ int r = sweep_out_(A, false), now = 0; for(int i = A.col_size() - 1; i >= 0; i--){ int pivot = -1; for(int j = now; j < r; j++){ if(A[j][i]) pivot = j; } if(pivot == -1) continue; swap(A[now], A[pivot]); for(int j = 0; j < r; j++){ if(j != now && A[j][i]) A[j] ^= A[now]; } now++; } vector> res(r,vector(A.col_size(),0)); for(int i = 0; i < r; i++){ for(int j = 0; j < A.col_size(); j++) if(A[i][j]) res[i][j] = true; } if(sorted) reverse(res.begin(), res.end()); return res; } vector solve_simultaneous_equation_(vector> &A , vector &b){ Matrix X(A), Y(b); return solve_simultaneous_equation_(X, Y); } vector solve_simultaneous_equation_(Matrix &A , vector &b){ Matrix Y(b); return solve_simultaneous_equation_(A, Y); } vector solve_simultaneous_equation_(vector> &A , Matrix &b){ Matrix X(A); return solve_simultaneous_equation_(X, b); } vector solve_simultaneous_equation_(Matrix &A , Matrix &b){ A.concat_col(b); return solve_simultaneous_equation_(A); } vector solve_simultaneous_equation_(vector> &A){ return solve_simultaneous_equation_(to_matrix(A)); } vector solve_simultaneous_equation_(Matrix &M){ int n = M.row_size() , m = M.col_size(); rank = sweep_out_(M,true); for(int row = rank ; row < n ; row++) if(M[row][n]) return {}; vector res; res.resize(rank); for(int i = 0 ; i < rank; i++) res[i] = M[i][m]; return solution = res; } public: GaussJordan(){} int sweep_out(Matrix &A) { return sweep_out_(A, false); } int sweep_out(Matrix &A, bool is_extended) { return sweep_out_(A, is_extended); } vector> create_xorbase(Matrix &A, bool sorted = false) { return create_xorbase_(A,sorted); } vector solve_simultaneous_equation(Matrix &A , Matrix &b) { return solve_simultaneous_equation_(A, b); } vector solve_simultaneous_equation(Matrix &A , vector &b) { return solve_simultaneous_equation_(A, b); } vector solve_simultaneous_equation(vector> &A , vector &b) { return solve_simultaneous_equation_(A, b); } vector solve_simultaneous_equation(vector> &A , Matrix &b) { return solve_simultaneous_equation_(A, b); } vector solve_simultaneous_equation(vector> &A) { return solve_simultaneous_equation_(A); } vector solve_simultaneous_equation(Matrix A) { return solve_simultaneous_equation_(A); } int get_rank() { return rank; } vector get_solution() { return solution; } }; const int mod = 998244353 ; ll powmod(ll x , ll n){ ll res = 1 ; while(n > 0){ if(n & 1) (res *= x) %= mod ; (x *= x) %= mod ; n >>= 1 ; } return res ; } int n, m; void solve(){ cin >> n >> m; set st; vector> A(2*m+1,vector(n,false)); rep(i,m){ int k; cin >> k; vector V; rep(j,k) { int a; cin >> a; a--; V.push_back(a); A[i][a] = true; A[i+m][a] = true; st.insert(a); } } rep(i,m){ for(int u : st) (A[i+m][u] = A[i+m][u] ? false : true); } rep(i,n) A[2*m][i] = true; Matrix mat(A); GaussJordan gj; int rank = gj.sweep_out(mat); pt(powmod(2,rank)) } int main(){ fast_io int t = 1; // cin >> t; rep(i,t) solve(); }