English · Original
Chinese · Translation
Formal · Original
Natalia Romanova is trying to test something on the new gun S.H.I.E.L.D gave her. In order to determine the result of the test, she needs to find the number of answers to a certain equation. The equation is of form:
Where represents logical OR and represents logical exclusive OR (XOR), and _v__i_, _j_ are some boolean variables or their negations. Natalia calls the left side of the equation a XNF formula. Each statement in brackets is called a clause, and _v__i_, _j_ are called literals.
In the equation Natalia has, the left side is actually a 2-XNF-2 containing variables _x_1, _x_2, ..., _x__m_ and their negations. An XNF formula is 2-XNF-2 if:
1. For each 1 ≤ _i_ ≤ _n_, _k__i_ ≤ 2, i.e. the size of each clause doesn't exceed two.
2. Each variable occurs **in the formula at most two times** (with negation and without negation in total). Please note that it's possible that a variable occurs twice but its negation doesn't occur in any clause (or vice versa).
Natalia is given a formula of _m_ variables, consisting of _n_ clauses. Please, make sure to check the samples in order to properly understand how the formula looks like.
Natalia is more into fight than theory, so she asked you to tell her the number of answers to this equation. More precisely, you need to find the number of ways to set _x_1, ..., _x__m_ with _true_ and _false_ (out of total of 2_m_ ways) so that the equation is satisfied. Since this number can be extremely large, you need to print the answer modulo 109 + 7.
Please, note that some variable may appear twice in one clause, or not appear in the equation at all (but still, setting it to _false_ or _true_ gives different ways to set variables).
## Input
The first line of input contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 100 000) — the number of clauses and the number of variables respectively.
The next _n_ lines contain the formula. The _i_\-th of them starts with an integer _k__i_ — the number of literals in the _i_\-th clause. It is followed by _k__i_ non-zero integers _a__i_, 1, ..., _a__i_, _k__i_. If _a__i_, _j_ > 0 then _v__i_, _j_ is _x__a__i_, _j_ otherwise it's negation of _x_ - _a__i_, _j_ (1 ≤ _k__i_ ≤ 2, - _m_ ≤ _a__i_, _j_ ≤ _m_, _a__i_, _j_ ≠ 0).
## Output
Print the answer modulo 1 000 000 007 (109 + 7) in one line.
[samples]
## Note
The equation in the first sample is:
The equation in the second sample is:
The equation in the third sample is:
娜塔莉亚·罗曼诺娃正在尝试测试 S.H.I.E.L.D 给她的新武器。为了确定测试结果，她需要求出某个方程的解的个数。该方程形式如下：
其中 $\lor$ 表示逻辑或，$\oplus$ 表示逻辑异或（XOR），而 $\text{cf\_span}[v_{i,j}]$ 是某些布尔变量或其否定。娜塔莉亚将方程的左侧称为 XNF 公式。括号内的每个子句称为一个子句，$\text{cf\_span}[v_{i,j}]$ 称为文字。
在娜塔莉亚给出的方程中，左侧实际上是一个 2-XNF-2 公式，包含变量 $\text{cf\_span}[x_1, x_2, \dots, x_m]$ 及其否定。一个 XNF 公式被称为 2-XNF-2，当且仅当：
娜塔莉亚给出了一个包含 $\text{cf\_span}[m]$ 个变量、由 $\text{cf\_span}[n]$ 个子句组成的公式。请务必查看样例，以便正确理解公式的结构。
娜塔莉亚更喜欢实战而非理论，因此她请你告诉她这个方程的解的个数。更准确地说，你需要计算有多少种方式将 $\text{cf\_span}[x_1, \dots, x_m]$ 设置为 $\text{cf\_span}[\text{true}]$ 和 $\text{cf\_span}[\text{false}]$（总共 $\text{cf\_span}[2^m]$ 种方式），使得方程成立。由于这个数字可能非常大，你需要输出对 $\text{cf\_span}[10^9 + 7]$ 取模的结果。
请注意，某个变量可能在同一个子句中出现两次，或者根本不出现在方程中（但即便如此，将其设为 $\text{cf\_span}[\text{false}]$ 或 $\text{cf\_span}[\text{true}]$ 仍被视为不同的赋值方式）。
输入的第一行包含两个整数 $\text{cf\_span}[n]$ 和 $\text{cf\_span}[m]$（$\text{cf\_span}[1 \leq n, m \leq 100\,000]$）——分别是子句数和变量数。
接下来的 $\text{cf\_span}[n]$ 行包含公式。第 $\text{cf\_span}[i]$ 行以一个整数 $\text{cf\_span}[k_i]$ 开头——表示第 $\text{cf\_span}[i]$ 个子句中文字的数量。其后跟着 $\text{cf\_span}[k_i]$ 个非零整数 $\text{cf\_span}[a_{i,1}, \dots, a_{i,k_i}]$。如果 $\text{cf\_span}[a_{i,j} > 0]$，则 $\text{cf\_span}[v_{i,j}]$ 是 $\text{cf\_span}[x_{a_{i,j}}]$；否则它是 $\text{cf\_span}[x_{-a_{i,j}}]$ 的否定（$\text{cf\_span}[1 \leq k_i \leq 2]$，$\text{cf\_span}[-m \leq a_{i,j} \leq m]$，$\text{cf\_span}[a_{i,j} \neq 0]$）。
请在一行中输出对 $\text{cf\_span}[1\,000\,000\,007]$（即 $\text{cf\_span}[10^9 + 7]$）取模的答案。
第一个样例中的方程是：
第二个样例中的方程是：
第三个样例中的方程是：
## Input
输入的第一行包含两个整数 $\text{cf\_span}[n]$ 和 $\text{cf\_span}[m]$（$\text{cf\_span}[1 \leq n, m \leq 100\,000]$）——分别是子句数和变量数。接下来的 $\text{cf\_span}[n]$ 行包含公式。第 $\text{cf\_span}[i]$ 行以一个整数 $\text{cf\_span}[k_i]$ 开头——表示第 $\text{cf\_span}[i]$ 个子句中文字的数量。其后跟着 $\text{cf\_span}[k_i]$ 个非零整数 $\text{cf\_span}[a_{i,1}, \dots, a_{i,k_i}]$。如果 $\text{cf\_span}[a_{i,j} > 0]$，则 $\text{cf\_span}[v_{i,j}]$ 是 $\text{cf\_span}[x_{a_{i,j}}]$；否则它是 $\text{cf\_span}[x_{-a_{i,j}}]$ 的否定（$\text{cf\_span}[1 \leq k_i \leq 2]$，$\text{cf\_span}[-m \leq a_{i,j} \leq m]$，$\text{cf\_span}[a_{i,j} \neq 0]$）。
## Output
请在一行中输出对 $\text{cf\_span}[1\,000\,000\,007]$（即 $\text{cf\_span}[10^9 + 7]$）取模的答案。
[samples]
## Note
第一个样例中的方程是：
第二个样例中的方程是：
第三个样例中的方程是：
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ be the number of clauses and variables, respectively.
Let $ \mathcal{F} $ be a 2-XNF-2 formula over variables $ x_1, \dots, x_m $, consisting of $ n $ clauses.
Each clause $ C_i $ is a disjunction (logical OR) of at most two literals:
- A literal is either $ x_j $ or $ \neg x_j $ for some $ j \in \{1, \dots, m\} $.
- Each clause has size $ k_i \in \{1, 2\} $, given by signed integers $ a_{i,1}, \dots, a_{i,k_i} \in [-m, m] \setminus \{0\} $, where positive values denote positive literals and negative values denote negated literals.
**Constraints**
1. $ 1 \leq n, m \leq 100{,}000 $
2. For each clause $ i $: $ 1 \leq k_i \leq 2 $
3. For each literal: $ -m \leq a_{i,j} \leq m $, $ a_{i,j} \ne 0 $
4. Variables not appearing in any clause still contribute to the total assignment space (i.e., all $ m $ variables are assigned independently).
**Objective**
Compute the number of assignments $ \sigma : \{x_1, \dots, x_m\} \to \{\text{true}, \text{false}\} $ such that $ \mathcal{F} $ evaluates to **true**, modulo $ 10^9 + 7 $.
That is, compute:
$$
\left| \left\{ \sigma \in \{0,1\}^m \,\middle|\, \bigwedge_{i=1}^n \bigvee_{j=1}^{k_i} \text{lit}_{i,j}(\sigma) = 1 \right\} \right| \mod (10^9 + 7)
$$
where $ \text{lit}_{i,j}(\sigma) $ is the truth value of the $ j $-th literal in clause $ i $ under assignment $ \sigma $.
API Response (JSON)
{
"problem": {
"name": "C. Black Widow",
"description": {
"content": "Natalia Romanova is trying to test something on the new gun S.H.I.E.L.D gave her. In order to determine the result of the test, she needs to find the number of answers to a certain equation. The equat",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF704C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Natalia Romanova is trying to test something on the new gun S.H.I.E.L.D gave her. In order to determine the result of the test, she needs to find the number of answers to a certain equation. The equat...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "娜塔莉亚·罗曼诺娃正在尝试测试 S.H.I.E.L.D 给她的新武器。为了确定测试结果，她需要求出某个方程的解的个数。该方程形式如下：\n\n其中 $\\lor$ 表示逻辑或，$\\oplus$ 表示逻辑异或（XOR），而 $\\text{cf\\_span}[v_{i,j}]$ 是某些布尔变量或其否定。娜塔莉亚将方程的左侧称为 XNF 公式。括号内的每个子句称为一个子句，$\\text{cf\\_span}[v...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z}^+ $ be the number of clauses and variables, respectively. \nLet $ \\mathcal{F} $ be a 2-XNF-2 formula over variables $ x_1, \\dots, x_m $, consisting of $ n $...",
"is_translate": false,
"language": "Formal"
}
]
}