娜塔莉亚·罗曼诺娃正在尝试用神盾局给她的新枪测试一些东西。为了确定测试的结果,她需要找到某个方程的答案数。方程的形式为:
$$( v _ { 1, 1 } \vee \ldots \vee v _ { 1, k _ { 1 } } ) \oplus ( v _ { 2, 1 } \vee \ldots \vee v _ { 2, k _ { 2 } } ) \oplus \ldots \oplus ( v _ { n, 1 } \vee \ldots \vee v _ { n, k _ { n } } ) = 1$$
其中$$\mathrm{~V~}$$表示逻辑或,$$\bigcirc$$表示逻辑异或(XOR),vi、j是一些布尔变量或其否定。 Natalia 将等式左边称为 XNF 公式。括号中的每个语句称为子句,vi、j 称为文字。
在 Natalia 的方程中,左边实际上是一个 2-XNF-2,包含变量 x1、x2、...、xm 及其负数。如果满足以下条件,XNF 公式为 2-XNF-2:
1. 对于每个 1 ≤ i ≤ n,ki ≤ 2,即每个子句的大小不超过 2。
2、每个变量在公式中最多出现两次(总共有否定和没有否定)。请注意,一个变量可能出现两次,但其否定不会出现在任何子句中(反之亦然)。
给 Natalia 一个包含 m 个变量的公式,由 n 个子句组成。请务必检查示例,以便正确理解公式的样子。
娜塔莉亚更喜欢战斗而不是理论,所以她要求你告诉她这个方程的答案数。更准确地说,您需要找到用 true 和 false 设置 x1, ..., xm 的方法数(总共 2m 种方法),以满足方程。由于这个数字可能非常大,因此您需要打印对 109 + 7 取模的答案。
请注意,某些变量可能在一个子句中出现两次,或者根本不会出现在方程中(但是,将其设置为 false 或 true 仍然会提供不同的设置变量的方法)。
输入
输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 100 000)——分别是子句的数量和变量的数量。
接下来的 n 行包含公式。其中第 i 个以整数 ki 开头——第 i 个子句中的文字数量。其后是 ki 个非零整数 ai, 1, ..., ai, ki。如果 ai, j > 0,则 vi, j 为 xai, j,否则为 x - ai, j 的负值 (1 ≤ ki ≤ 2, - m ≤ ai, j ≤ m, ai, j ≠ 0)。
输出
将答案以 1 000 000 007 (109 + 7) 为模打印在一行中。
示例
输入 #1
6 7 2 4 -2 2 6 3 2 -7 1 2 -5 1 2 3 6 2 -2 -5
输出 #1
48
输入 #2
8 10 1 -5 2 4 -6 2 -2 -6 2 -7 9 2 10 -1 2 3 -1 2 -8 9 2 5 8
输出 #2
544
输入 #3
2 3 2 1 1 2 -3 3
输出 #3
4
注意
第一个示例中的方程为:
$$( x _ { 4 } \vee \overline { { x _ { 2 } } } ) \oplus ( x _ { 6 } \vee x _ { 3 } ) \oplus ( \overline { { x _ { 7 } } } \vee x _ { 1 } ) \oplus ( \overline { { x _ { 5 } } } \vee x _ { 6 } ) \oplus ( \overline { { x _ { 2 } } } \vee \overline { { x _ { 5 } } } ) = 1$$
第二个示例中的方程为:
$$( \overline { x _ { 5 } } ) \oplus ( x _ { 4 } \lor \overline { x _ { 6 } } ) \oplus ( \overline { x _ { 2 } } \lor \overline { x _ { 6 } } ) \oplus ( \overline { x _ { 7 } } \lor x _ { 9 } ) \oplus ( x _ { 1 0 } \lor \overline { x _ { 1 } } ) \oplus ( x _ { 3 } \lor \overline { x _ { 1 } } ) \oplus ( \overline { x _ { 8 } } \lor x _ { 9 } ) \oplus ( x _ { 5 } \lor x _ { 8 } ) = 1$$
第三个示例中的方程为:
$$( x _ { 1 } \vee x _ { 1 } ) \oplus ( \overline { x _ { 3 } } \vee x _ { 3 } ) = 1$$