10.18 学校模拟赛 T4

题意：有一个含 \(\text{NaN}\) 的排列 \(1, 2, 3, \dots, n-1, \text{NaN}\)。其中 \(n=1\) 时排列有一个元素 \(\text{NaN}\)。求这个排列构成小根堆的概率，对 \(10^9+7\) 取模。
一个排列 \(a\) 构成小根堆，当且仅当对于所有 \(2 \le i \le n\)，满足 \(a_i < a_{\lfloor i/2 \rfloor}\) 不成立。而 \(\text{NaN}\) 与任何数比较的结果都是 false。
\(T\) 组数据，\(n \le 10^9,T \le 10^3\)。