题目描述

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$ 取模的值。

3
2
8
29

2
6720
195120252

提示

样例解释

对于样例一，最少应当使用 $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$		符合
$2$	$15$	$\le 10^5$	$\le 10^6$
$3$	$28$	$\le 1000$		不符合
$4$	$22$	$\le 10^5$	$\le 10^6$

对于符合特殊性质的测试点，保证存在整数 $k$，使得 $2^k = n$。