CF1737E.Ela Goes Hiking

Ela likes to go hiking a lot. She loves nature and exploring the various creatures it offers. One day, she saw a strange type of ant, with a cannibalistic feature. More specifically, an ant would eat any ants that it sees which is smaller than it.

Curious about this feature from a new creature, Ela ain't furious. She conducts a long, non-dubious, sentimental experiment.

She puts $n$ cannibalistic ants in a line on a long wooden stick. Initially, the ants have the same weight of $1$. The distance between any two consecutive ants is the same. The distance between the first ant in the line to the left end and the last ant in the line to the right end is also the same as the distance between the ants. Each ant starts moving towards the left-end or the right-end randomly and equiprobably, at the same constant pace throughout the experiment. Two ants will crash if they are standing next to each other in the line and moving in opposite directions, and ants will change direction immediately when they reach the end of the stick. Ela can't determine the moving direction of each ant, but she understands very well their behavior when crashes happen.

• If a crash happens between two ants of different weights, the heavier one will eat the lighter one, and gain the weight of the lighter one. After that, the heavier and will continue walking in the same direction. In other words, if the heavier one has weight $x$ and walking to the right, the lighter one has weight $y$ and walking to the left ($x \gt y$), then after the crash, the lighter one will diminish, and the heavier one will have weight $x + y$ and continue walking to the right.
• If a crash happens between two ants with the same weight, the one walking to the left end of the stick will eat the one walking to the right, and then continue walking in the same direction. In other words, if one ant of weight $x$ walking to the left, crashes with another ant of weight $x$ walking to the right, the one walking to the right will disappear, and the one walking to the left will have to weight $2x$ and continue walking to the left.

Please, check the example in the "Note" section, which will demonstrate the ants' behavior as above.

We can prove that after a definite amount of time, there will be only one last ant standing. Initially, each ant can randomly and equiprobably move to the left or the right, which generates $2^n$ different cases of initial movements for the whole pack. For each position in the line, calculate the probability that the ant begins in that position and survives. Output it modulo $10^9 + 7$.

Formally, let $M = 10^9 + 7$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output such an integer $x$ that $0 \le x \lt M$ and $x \cdot q \equiv p \pmod{M}$.

Ela 非常喜欢徒步旅行。她热爱大自然，也热衷于探索其中形形色色的生物。某天，她发现了一种奇特的蚂蚁，具有同类相食的习性：具体而言，一只蚂蚁会吃掉它视野中所有比它体型小的蚂蚁。

出于对这种新奇生物特性的强烈好奇，Ela 并未感到愤怒，而是开展了一项漫长、严谨且饱含情感的实验。

她将 $n$ 只同类相食的蚂蚁排成一列，放置在一根长长的木棍上。初始时，所有蚂蚁的重量均为 $1$。任意两只相邻蚂蚁之间的距离均相等；且最左侧蚂蚁到木棍左端的距离、以及最右侧蚂蚁到木棍右端的距离，也都等于该相邻间距。每只蚂蚁以相同且恒定的速度，独立地、等概率地随机选择向左端或右端移动。若两只蚂蚁在队列中彼此相邻且朝相反方向运动，则它们将发生碰撞；而当任意蚂蚁抵达木棍端点时，会立即掉头反向运动。Ela 无法预先得知每只蚂蚁的初始运动方向，但她对碰撞发生时蚂蚁的行为规律了如指掌：

• 若两只重量不同的蚂蚁发生碰撞，则较重者将吃掉较轻者，并吸收其全部重量。此后，较重者继续沿原方向前进。换言之，若较重蚂蚁重量为 $x$、向右运动，较轻蚂蚁重量为 $y$、向左运动（满足 $x > y$），则碰撞后较轻蚂蚁消失，较重蚂蚁重量变为 $x + y$，并继续向右运动。
• 若两只重量相同的蚂蚁发生碰撞，则朝木棍左端运动的蚂蚁将吃掉朝右端运动的蚂蚁，并继续向左运动。换言之，若一只重量为 $x$ 的蚂蚁向左运动，与另一只重量同为 $x$ 的蚂蚁向右运动发生碰撞，则向右运动的蚂蚁消失，向左运动的蚂蚁重量变为 $2x$，并继续向左运动。

请参阅“注”部分中的示例，该示例将直观展示上述蚂蚁行为。

可以证明：经过一段确定的时间后，最终仅剩一只蚂蚁存活。初始时，每只蚂蚁独立地、等概率地选择向左或向右运动，因此整个蚁群共有 $2^n$ 种可能的初始运动状态。对队列中每个位置，请计算：位于该位置的蚂蚁在初始时刻即处于该位置且最终存活的概率。答案需对 $10^9 + 7$ 取模输出。

形式化地，令 $M = 10^9 + 7$。可以证明，所求答案可表示为既约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 均为整数，且 $q \not\equiv 0 \pmod{M}$。请输出整数 $p \cdot q^{-1} \bmod M$。换言之，请输出唯一满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.

The only line of each test contains an integer $n$ ($1 \le n \le 10^6$) — the number of ants in the experiment.

It is guaranteed that the sum of $n$ in all tests will not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^3$）。随后是各测试用例的描述。

每个测试用例仅一行，包含一个整数 $n$（$1 \le n \le 10^6$）——实验中蚂蚁的数量。

保证所有测试用例中 $n$ 的总和不超过 $10^6$。

For each test, print $n$ lines. $i$-th line contains a single number that denotes the survival probability of the $i$-th ant in the line modulo $10^9 + 7$.

对于每组测试，输出 $n$ 行。第 $i$ 行包含一个数字，表示队列中第 $i$ 只蚂蚁的存活概率对 $10^9 + 7$ 取模的结果。

Here is the example of $6$ ants moving on the branch. An ant's movement will be denoted by either a character $L$ or $R$. Initially, the pack of ants on the branch will move as $RLRRLR$. Here's how the behavior of the pack demonstrated:

Initially, the ants are positioned as above.

After a while, the ant with index $2$ (walking to the left) will crash with the ant with index $1$ (walking to the right). The two ants have the same weight, therefore, ant $2$ will eat ant $1$ and gain its weight to $2$. The same thing happens with ant $5$ and ant $4$.

The ant $6$ will walk to the end of the stick, therefore changing its direction.

After that, the ant with index $5$ will crash with the ant with index $3$. Since ant $5$ is more heavy (weight=$2$) than ant $3$ (weight=$1$), ant $5$ will eat ant $3$ and gain its weight to $3$.

Ant $2$ will walk to the end of the stick, therefore changing its direction.

After that, the ant with index $5$ will crash with the ant with index $2$. Since ant $5$ is more heavy (weight=$3$) than ant $2$ (weight=$2$), ant $5$ will eat ant $2$ and gain its weight to $5$.

Lastly, after ant $5$ walk to the end of the branch and changes its direction, ant $5$ will eat ant $6$ and be the last ant standing.

以下是 $6$ 只蚂蚁在树枝上移动的示例。每只蚂蚁的运动方向用字符 $L$ 或 $R$ 表示。初始时，树枝上这群蚂蚁的运动序列为 $RLRRLR$。其行为演化过程如下所示：

初始时，蚂蚁的位置如上图所示。

一段时间后，编号为 $2$ 的蚂蚁（向左行走）将与编号为 $1$ 的蚂蚁（向右行走）发生碰撞。由于两只蚂蚁质量相等，因此蚂蚁 $2$ 将吃掉蚂蚁 $1$，并将其质量增加至 $2$。蚂蚁 $5$ 与蚂蚁 $4$ 之间也发生了同样的情况。

蚂蚁 $6$ 将行走至树枝末端，从而改变其运动方向。

此后，编号为 $5$ 的蚂蚁将与编号为 $3$ 的蚂蚁发生碰撞。由于蚂蚁 $5$ 的质量（为 $2$）大于蚂蚁 $3$ 的质量（为 $1$），蚂蚁 $5$ 将吃掉蚂蚁 $3$，并将其质量增加至 $3$。

蚂蚁 $2$ 将行走至树枝末端，从而改变其运动方向。

随后，编号为 $5$ 的蚂蚁将与编号为 $2$ 的蚂蚁发生碰撞。由于蚂蚁 $5$ 的质量（为 $3$）大于蚂蚁 $2$ 的质量（为 $2$），蚂蚁 $5$ 将吃掉蚂蚁 $2$，并将其质量增加至 $5$。

最后，当蚂蚁 $5$ 行走至树枝末端并改变方向后，它将吃掉蚂蚁 $6$，成为唯一存活的蚂蚁。