SP31897 IFCHAIN - If Chain

Consider the following code: ``` if (a) if (b) if (c) foo(); ``` where _a,b_ and _c_ are boolean variables. If we run this code in C++, the function _foo()_ is called if and only if all three variables are true. However, recently a new language - C-- - is being developed. In this language, when an _if()_ evaluates to false, only the statement directly following it is not executed; for example, if _a_ was false, the program would jump from _if(a)_ to _if(c)_. Using this convention, there are 5 different possible assignments of truth values to the variables _a_,_b_,_c_ which end up calling _foo()_. Considering _a_,_b_,_c_ as three bits in that order, they are 111, 101, 100, 011 and 001. Given **n** boolean variables within a chain of **m** _if()_'s, where the variables within one _if()_ are separated using **logical or**, count the number of ways to assign truth values to them which end up calling the function _foo()_ (the call to _foo()_ is after the last _if()_).

The first line of the input is the number of test cases **1 **T . **T** test cases follow.**** The first line of each test case contains two nonnegative integers **n - the number of boolean variables (they are numbered **1** through **n**) - and **m - the number of _if()_'s. **m** lines follow, the **i**-th line describing the **i**-th _if()_. The first integer in each line is a positive integer **k $ _{i} $** - the number of variables in the **i**-th _if()_ (implicitly separated by the **logical or** operator) - followed by **k $ _{i} $** positive integers in the range **\[1,n\]**: the variables in the **i**-th _if()_. Not all variables need necessarily appear within the _if()_ chain, and the variables within one _if()_ need not be distinct.**** The sum of **k $ _{i} $** within a test case will not exceed **5\*10 $ ^{5} $** . Additionally, the sum of **n**,**m** and **k $ _{i} $ $ _{ } $** within a single input file will not exceed **2\*10 $ ^{6} $ .** **The input is quite large - make sure to read it efficiently.**

For each case, output the string "Case **x**: **y**" in a single line, where **x** is the number of the test case, starting from 1, and **y** is the number of ways of assigning truth values to the **n** boolean variables (out of **2 $ ^{n} $** ), which when run in C-- end up calling _foo()_, modulo **10 $ ^{9} $ +9**.