SP31897 IFCHAIN - If Chain

考虑下面这段代码： ``` if (a) if (b) if (c) foo(); ``` 其中 $a$、$b$ 和 $c$ 是布尔变量。在 C++ 中运行这段代码时，只有当所有变量均为真时，函数 $foo()$ 才会被调用。然而，近期正在开发一种新的编程语言 C--。在 C-- 中，如果某个 $if()$ 条件判断为假，只有紧随其后的那条语句不被执行；例如，当 $a$ 为假时，程序会直接跳过到 $if(c)$。 按照这种规则，有 5 种不同的布尔变量 $a$、$b$、$c$ 的组合可以最终调用 $foo()$。将 $a$、$b$、$c$ 视为三个顺序排列的比特位，它们分别是 111、101、100、011 和 001。 现在，给定 **n** 个布尔变量和一个由 **m** 个 $if()$ 语句构成的链式结构，其中每个 $if()$ 内的变量通过逻辑或运算符连接。要求你计算有多少种变量的赋值方式可以让程序最终调用 $foo()$ 函数（位于最后一个 $if()$ 之后）。

第一行为一个整数 **T**，表示测试用例的数量。接下来是 **T** 组测试用例。 每个测试用例的第一行包含两个非负整数 **n** 和 **m**，分别表示布尔变量的数量（编号从 1 到 **n**）以及 $if()$ 语句的数量。接下来的 **m** 行， 每行描述一个 $if()$ 语句。行的第一个整数 **k $_{i}$** 代表第 i 个 $if()$ 中变量的数量（这些变量通过逻辑或运算符连接），接下来的 **k $_{i}$** 个整数表示范围在 [1, n] 内的变量编号。并不是所有的变量都必须出现于 $if()$ 语句链中，同一个 $if()$ 中的变量也可以重复。 在一个测试用例中，所有 **k $_{i}$** 值的总和不超过 5 × 10$^{5}$。同时，单个输入文件中所有的 **n**、**m** 和 **k $_{i}$** 的总和不超过 2 × 10$^{6}$。 由于输入数据量较大，需注意高效读取。

对于每个测试用例，输出一行字符串 "Case **x**: **y**"，其中 **x** 是测试用例的编号（从 1 开始），而 **y** 是能够让 C-- 程序调用 $foo()$ 的布尔变量赋值方式的数量，这一结果需对 10$^{9}$ + 9 取模。 **本翻译由 AI 自动生成**