Infinite Virtue

In this problem you are given a set of cyber Buddhas. There are initially (n) Buddhas numbered from (1) to (n). The (i)th Buddha is associated with a pair (\langle S_i, d_i\rangle) where (S_i) is a subset of ({1,2,\dots,m}) (possibly empty) and (d_i) is an integer between (1) and (m). The system evolves in discrete time steps. At any time, if there exists a Buddha whose set is empty, then the one with the smallest index becomes happy and rings the wooden fish corresponding to its (d_i). In the next moment this event causes all Buddhas (including the one that rang the fish) to update their sets in the following way: [ \text{For each }j:\quad S_j := \begin{cases} S_j\setminus{d_i} & \text{if } d_i\in S_j,\ S_j\cup{d_i} & \text{if } d_i \notin S_j. \end{cases} ] To achieve infinite virtue (i.e. to guarantee that at every step there is always at least one Buddha with an empty set) you are allowed to recruit additional Buddhas. If you add (s) new Buddhas (numbered (n+1,n+2,\dots,n+s)), you may choose their pairs (\langle S, d\rangle) arbitrarily. Of course, as a capitalist you wish to minimize the number (s) needed so that the process never stops.

There are many queries. For each query defined by two integers (l) and (r) (with (1\le l\le r\le n)) consider the system that initially consists only of Buddhas with numbers in ([l,r]). Let (f(l,r)) be the minimum number (s) of extra Buddhas needed to ensure that the process continues indefinitely. (Note that extra Buddhas added in one query do not carry over to later queries.)

It can be shown that the answer in each case is given by [ f(l,r)=\min{\mathrm{popcount}(S): S \text{ is one of the } S_i \text{ for } l \le i \le r},, ] where (\mathrm{popcount}(S)) denotes the number of elements in (S) (with the convention that the popcount of the empty set is (0)).

Your task is to compute [ \sum_{l=1}^{n}\sum_{r=l}^{n} f(l,r)\times2^l \pmod{10^9+7}. ]

Note: All formulas are given in (\LaTeX) format and the input format is described below.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \le n \le 10^5\), \(1 \le m \le 20\)). Each of the next \(n\) lines describes one Buddha. The \(i\)th of these lines begins with an integer \(k_i\) (\(0\le k_i\le m\)), the size of \(S_i\). If \(k_i > 0\), it is followed by \(k_i\) distinct integers in the range \([1,m]\) denoting the elements of \(S_i\). Finally, an integer \(d_i\) (which you may ignore for the purpose of computing \(f(l,r)\)) is given.

Note: Although each Buddha has an associated value \(d_i\), the answer depends only on the sets \(S_i\) (via their popcount, where the popcount of the empty set is \(0\)).

outputFormat

Output a single integer: the value of \(\sum_{l=1}^{n}\sum_{r=l}^{n} f(l,r) \times 2^l \pmod{10^9+7}\).

sample

3 3
0 1
2 1 2 2
1 3 3

20