P13240 「2.48sOI R1」猜数

Misserina 有一个小于 $n$ 的自然数 $x$，而 lizihan250 并不知道 $x$ 的值。 现在，lizihan250 准备了 $m$ 张卡片，每张卡片上都写有一些互不相同的**小于 $n$ 的**数字。接着，Misserina 会告诉 lizihan250 $x$ 在哪些卡片上出现，而另外的卡片上 $x$ 未出现。lizihan250 需要根据 Misserina 提供的信息，猜出 $x$ 的值。 如果每次都用一套卡片，这个游戏将变得很枯燥。因此，lizihan250 想知道，在保证根据 Misserina 提供的信息一定能猜出唯一确定的 $x$，且 $m$ 最小的情况下，有多少种不同的在卡片上写数字的方式？两种方式相同，当且仅当它们使用的卡片数相同，且交换一种方式中卡片的前后顺序可以得到另外一种方式。答案对 $10^9+7$ 取模。 ### 形式化题意 一个集合 $A$ 是“好的集合”，当且仅当集合 $A$ 包含若干个由一些自然数组成的集合，且对于 $\forall 0 \le i < j < n (i,j \in \mathbb{N})$，$A$ 中至少存在一个集合 $B$，使得 $i \in B$ 且 $j \notin B$，或 $i \notin B$ 且 $j \in B$。 令“好的集合”$A$ 的元素数量最小值为 $m$，试求出满足 $|A| = m$ 的“好的集合”$A$ 的数量，并对 $10^9+7$ 取模。

**一个测试点中含有多个互相独立的测试数据。** 第一行，一个正整数 $t$，表示测试数据的数量。 接下来 $t$ 行，每行一个正整数 $n$。

共 $t$ 行，每行一个整数，第 $i$ 行的数表示第 $i$ 组测试数据的答案数对 $10^9+7$ 取模的值。

### 样例解释 对于样例一，最少应当使用 $1$ 张卡片，有如下两种方案： 1. 在这张卡片上只写下一个 $0$。此时，若 Misserina 回答“在这张卡片上存在 $x$”，则 $x=0$，否则 $x=1$。 2. 在这张卡片上只写下一个 $1$，跟上一种情况相反。 对于样例二，最少应当使用 $3$ 张卡片，一种方案为三张卡片分别包含 $\{1,2,3,7\},\{1,2,5,6\}$ 和 $\{1,3,4,5\}$。 ### 数据规模与约束 **本题采用捆绑测试** 对于 $100\%$ 的数据，有 $1 \le n \le 10^6$。 | Subtask 编号 | 分值 | $t$ | $n$ | 特殊性质 | | :----------: | :--: | :-: | :-: | :------: | | $0$ | $23$ | $\le 10$ | $\le 8$ | 不符合 | | $1$ | $12$ | $\le 1000$ | $\le 1000$ | 符合 | | $2$ | $15$ | $\le 10^5$ | $\le 10^6$ | 符合 | | $3$ | $28$ | $\le 1000$ | $\le 1000$ | 不符合 | | $4$ | $22$ | $\le 10^5$ | $\le 10^6$ | 不符合 | 对于符合特殊性质的测试点，保证存在整数 $k$，使得 $2^k = n$。