Minimum Number of Sets in a Boolean Algebra

Given an integer n and m non-empty subsets of the universal set \(U = \{1, 2, \dots, n\}\), a collection of sets is said to be closed under complement and union if it satisfies the following properties:

• If a set \(A\) is in the collection, then its complement \(U\setminus A\) is also in the collection.
• If sets \(A\) and \(B\) are in the collection, then their union \(A \cup B\) is also in the collection.

The collection must contain the given m sets. Note that due to closure under complement, the collection will necessarily contain both \(\varnothing\) and \(U\) (even though the given sets are non-empty). Such a collection is essentially the Boolean algebra generated by the given sets.

It is known that if every element \(x \in U\) is associated with an m-bit binary vector indicating its membership in each given set, then the Boolean algebra generated by these sets consists of all unions of atoms (i.e. the nonempty parts in the partition of \(U\) determined by these binary vectors). Let \(r\) be the number of distinct binary vectors that actually appear among the elements of \(U\). Then the complete Boolean algebra has exactly \(2^r\) sets.

Your task is to compute \(2^r \bmod (10^9+9)\), which is the minimum number of sets in such a collection (including \(\varnothing\) and \(U\)).

inputFormat

The first line contains two integers \(n\) and \(m\): the size of the universal set \(U = \{1, 2, \dots, n\}\) and the number of given sets.

Then, m lines follow. Each line begins with an integer \(k\) (the number of elements in the set) followed by \(k\) distinct integers representing the elements that belong to the set.

outputFormat

Output a single integer: \(2^r \bmod (10^9+9)\), where \(r\) is the number of distinct membership patterns among the elements of \(U\).

sample

5 2
2 1 2
3 2 3 5

16