P14163 [ICPC 2022 Nanjing R] 堆里的 NaN

$$\textbf{预备知识：NaN}$$ $\texttt{NaN}$ (Not a Number) 是 1985 年 IEEE 754 浮点数标准里引入的特殊浮点数。标准规定，当 $\texttt{NaN}$ 与一个浮点数 $\texttt{x}$ 进行比较时（$\texttt{x}$ 可以是正数，零，负数，甚至是 $\texttt{NaN}$ 本身），应当返回以下结果。 $$ \begin{array}{|c|c|c|c|c|c|c|} \hline \textbf{比较} & \texttt{NaN} \ge \texttt{x} & \texttt{NaN} \le \texttt{x} & \texttt{NaN} > \texttt{x} & \texttt{NaN} < \texttt{x} & \texttt{NaN} = \texttt{x} & \texttt{NaN} \ne \texttt{x} \\ \hline \textbf{结果} & False & False & False & False & False & True \\ \hline \end{array} $$ $$\textbf{预备知识：堆}$$ 堆是一种数据结构，可以用具有特殊性质的序列表示。以下算法展示了如何将 $n$ 个浮点数 $a_1, a_2, \cdots, a_n$ 按顺序加入小根堆 $H$ 中，其中 $H$ 是一个初始为空的序列。 以下算法中，用 $h_i$ 表示 $H$ 的第 $i$ 个元素，用 $j/2$ 表示满足 $2x \le j$ 的最大整数 $x$。 :::align{center}  ::: $$\textbf{问题}$$ 给定一个整数 $n$，考察这 $n$ 个元素的排列：从 $1$ 到 $(n - 1)$ 的所有整数（含两端），再加上一个额外的元素 $\texttt{NaN}$。称这 $n$ 个元素的一个排列 $P$ 是“堆序列”，若存在这 $n$ 个元素的一个排列 $Q$ 满足 $P = \text{\texttt{HEAPIFY}}(Q)$。 现在从这 $n$ 个元素的所有排列中等概率随机选取一个（也就是说，一个特定的排列被选中的概率是 $\frac{1}{n!}$），求被选中的排列是堆序列的概率。

有多组测试数据。第一行输入一个整数 $T$（$1 \le T \le 10^3$）表示测试数据组数，对于每组测试数据： 第一行输入一个整数 $n$（$1 \le n \le 10^9$）。

每组数据输出一行表示答案。 可以证明答案是一个有理数 $\frac{p}{q}$。为了避免精度问题，请输出整数 $(pq^{-1} \bmod M)$ 作为答案，其中 $M = 10^9 + 7$，$q^{-1}$ 是满足 $qq^{-1} \equiv 1 \pmod M$ 的整数。

对于第二组样例数据，有 $4$ 个堆序列。 - $\{\texttt{NaN}, 1, 2\} = \text{\texttt{HEAPIFY}}(\{\texttt{NaN}, 1, 2\})$。 - $\{\texttt{NaN}, 2, 1\} = \text{\texttt{HEAPIFY}}(\{\texttt{NaN}, 2, 1\})$。 - $\{1, \texttt{NaN}, 2\} = \text{\texttt{HEAPIFY}}(\{1, \texttt{NaN}, 2\}) = \text{\texttt{HEAPIFY}}(\{2, \texttt{NaN}, 1\})$。 - $\{1, 2, \texttt{NaN}\} = \text{\texttt{HEAPIFY}}(\{1, 2, \texttt{NaN}\}) = \text{\texttt{HEAPIFY}}(\{2, 1, \texttt{NaN}\})$。 所以答案用有理数表示是 $\frac{4}{3!} = \frac{2}{3}$。因为 $3 \times 333333336 \equiv 1 \pmod M$，我们应该输出 $2 \times 333333336 \bmod M = 666666672$。