T566555 「PA Mashup #1」归约

我们给定 SAT 问题的定义。本题中，不区分 $1$ 与 $\mathrm{True}$，$0$ 与 $\mathrm{False}$。 SAT 问题用来求出一组逻辑变量 $x_1,x_2,\cdots,x_n$ 的取值（其中 $x_i\in \{\mathrm{True},\mathrm{False}\}$），使得以下的**合取范式**取值为真： $$(l_{1,1}\lor l_{1,2}\lor \ldots\lor l_{1,q_1})\land (l_{2,1}\lor l_{2,2}\lor \ldots\lor l_{2,q_2})\land \ldots \land (l_{m,1}\lor l_{m,2}\lor \ldots\lor l_{m,q_m})$$ 其中，$(l_{i,1}\lor l_{i,2}\lor \ldots\lor l_{i,q_i})$ 称为**子句**（Clause），$l_{i,j}$ 是 $x_1,\ldots,x_n$ 中的变量或其否定。我们规定一个子句中，不存在 $j\lt k$，使得 $l_{i,j}$ 中的变量与 $l_{i,k}$ 中的变量相同。 --- 某人声称解决了世界难题 $\mathrm{P}=\mathrm{NP?}$。他声称，一般的 SAT 问题都可以归约到一种特例，而这种特例中的所有子句都满足特殊性质： - $\forall 1\le i\le n$，$x_i$ 和 $\neg x_i$ 不会同时在子句中出现。 - $\forall 1\le i\lt j\lt k\le n$，若子句中出现了 $x_i$（或 $\neg x_i$）和 $x_k$（或 $\neg x_k$），则必然有 $x_j$（或 $\neg x_j$）在这个子句中出现。 这里，所有出现的变量的下标都是 $1\sim n$。 给定满足特例的合取范式，统计有多少种不同的取值能够使其取值为真。只需要求出答案对 $(10^9+7)$ 取模后的结果。

无

无

#### 样例解释 两个合法解为 $(0,1,1)$ 和 $(1,1,1)$。 #### 数据范围 - $1\le n\le 10^6$； - 所有子句中变量个数的和不超过 $10^6$。