#include // clang-format off using namespace std;constexpr int INF=1001001001;constexpr long long INFll=1001001001001001001;namespace viewer{using s=string;templates f(T i){s S=i==INF||i==INFll?"inf":to_string(i);return s(max(0,3-int(S.size())),' ')+S;} templateauto v(T&x,s&&e)->decltype(cerr<void v(const pair&p,s&&e="\n"){cerr<<"(";v(p.first,", ");v(p.second,")"+e);}templatevoid v(const tuple&t,s&&e="\n"){cerr<<"(";v(get<0>(t),", ");v(get<1>(t),")"+e);}templatevoid v(const tuple&t,s&&e="\n"){cerr<<"(";v(get<0>(t),", ");v(get<1>(t),", ");v(get<2>(t),")"+e);}templatevoid v(const tuple&t,s&&e="\n"){cerr<<"(";v(get<0>(t),", ");v(get<1>(t),", ");v(get<2>(t),", ");v(get<3>(t),")"+e);} templatevoid v(const vector&vx,s);templateauto ve(int,const vector&vx)->decltype(cerr<auto ve(bool,const vector&vx){cerr<<"{\n";for(const T&x:vx)cerr<<" ",v(x,",");cerr<<"}\n";}templatevoid v(const vector&vx,s){ve(0,vx);} templatevoid v(const deque&q,s&&e){v(vector(q.begin(),q.end()),e);}templatevoid v(const set&S,s&&e){v(vector(S.begin(),S.end()),e);}templatevoid v(const multiset&S,s&&e){v(vector(S.begin(),S.end()),e);}templatevoid v(const unordered_set&S,s&&e){v(vector(S.begin(),S.end()),e);} templatevoid v(const priority_queue&p,s&&e){priority_queueq=p;vectorz;while(!q.empty()){z.push_back(q.top());q.pop();}v(z,e);}templatevoid v(const map&m,s&&e){cerr<<"{"<<(m.empty()?"":"\n");for(const auto&kv:m){cerr<<" [";v(kv.first,"");cerr<<"] : ";v(kv.second,"");cerr<<"\n";}cerr<<"}"+e;} templatevoid _view(int n,s&S,T&var){cerr<<"\033[1;32m"<void grid([[maybe_unused]]T _){}void grid(const vector>&vvb){cerr<<"\n";for(const vector&vb:vvb){for(const bool&b:vb)cerr<<(b?".":"#");cerr<<"\n";}} void _debug(int,s){}templatevoid _debug(int n,s S,const H&h,const T&... t){int i=0,cnt=0;for(;iap;mint re=a;for(long long r=1;r // clang-format off struct matrix{ vector>A; static matrix I(int n){matrix mat(n);for(int i=0;i>&vvec){A=vvec;} matrix(int n,int m):A(n,vector(m,0)){} matrix(int n,int m,T init):A(n,vector(m,init)){} matrix(int n,vector&vec):A(n,vec){} matrix(int n):A(n,vector(n,0)){} int height()const{return A.size();} int width()const{return A[0].size();} inline vector&operator[](int k){return A[k];} bool operator==(const matrix&B){int n=height(),m=width();if(n!=B.height()or m!=B.width())return false;for(int i=0;i>C(n,vector(m,0));for(int i=0;i0){if(k&1)B*=(*this);*this*=*this;k>>=1ll;}A.swap(B.A);return*this;} matrix operator+(const matrix&B)const{return(matrix(*this)+=B);} matrix operator-(const matrix&B)const{return(matrix(*this)-=B);} matrix operator*(const matrix&B)const{return(matrix(*this)*=B);} matrix operator^(const long long&k)const{return(matrix(*this)^=k);} matrix&operator+=(const T&t){int n=height(),m=width();for(int i=0;i0&&m>0);os<<" (h:"<=0;i--){sigma=y[i][h];for(int j=i+1;jLU_decomposition(){assert(height()==width());int n=height();matrix A(*(this));vectorp(n);for(int i=0;i=0?A[p[i]][k]:-A[p[i]][k]);if(absolute>=max_a)max_a=absolute,best_i=i;}int i=best_i;swap(p[i],p[k]);T w=T(1)/A[p[k]][k];for(int i=k+1;ij?A[p[i]][j]:T(0));U[i][j]=(i<=j?A[p[i]][j]:T(0));}L[i][i]=T(1);P[i][p[i]]=T(1);}return{P,L,U};} }; // clang-format on template int Gauss_Jordan(matrix& m) { assert(m.is_binary()); int rank = 0; for (int col = 0; col < m.width(); col++) { int pivot = -1; for (int row = rank; row < m.height(); row++) if (m[row][col]) { pivot = row; break; } if (pivot == -1) continue; swap(m.A[pivot], m.A[rank]); for (int row = 0; row < m.height(); row++) if (row != rank && m[row][col]) for (int c = 0; c < m.width(); c++) m.A[row][c] ^= m.A[rank][c]; assert(m.A[rank][col]); // rank行col列に必ず1が存在する rank++; } return rank; } /* 行列累乗テンプレ: int N; cin >> N; long long exp = 100000000000; matrix init(N, 1); matrix mat(N, N); init[0][0] = mint(1); mat ^= exp; matrix ans = mat * init; */ int main() { cin.tie(0); ios::sync_with_stdio(false); int N, M; cin >> N >> M; vector> s(N, vector(M, -1)); for (int i = 0; i < M; i++) { int L; cin >> L; vector As(N); for (int j = 0; j < L; j++) { cin >> As[j]; As[j]--; s[As[j]][i] = 1; } } debug(s); sort(s.begin(), s.end()); s.erase(unique(s.begin(), s.end()), s.end()); cout << mint(2).pow(s.size()) << endl; return 0; }