Ela 非常喜欢徒步旅行。她热爱大自然并探索它提供的各种生物。有一天,她看到一种奇怪的蚂蚁,具有同类相食的特征。更具体地说,蚂蚁会吃掉它看到的任何比它小的蚂蚁。埃拉对新生物的这一功能感到好奇,但她并没有生气。她进行了一项漫长的、毫无疑问的、感性的实验。
她把$$$n$$$同类相食的蚂蚁放在一根长木棍上排成一排。最初,蚂蚁的重量相同,均为$$$1$$$。任何连续的两只蚂蚁之间的距离是相同的。到左端的行中第一只蚂蚁和到右端的行中的最后一只蚂蚁之间的距离也与蚂蚁之间的距离相同。在整个实验过程中,每只蚂蚁开始以相同的恒定速度随机且等概率地向左端或右端移动。如果两只蚂蚁站在一条线上并朝相反的方向移动,它们就会相撞,而当蚂蚁到达棍子末端时,它们会立即改变方向。艾拉无法确定每只蚂蚁的移动方向,但她非常了解它们在发生碰撞时的行为。
- 如果两只不同重量的蚂蚁发生碰撞,较重的蚂蚁会吃掉较轻的蚂蚁,并增加较轻蚂蚁的重量。之后,更重的,会继续朝同一个方向行走。换句话说,如果较重的重量 $$$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$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。
每个测试的唯一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — 实验中蚂蚁的数量。
保证所有测试中$$$n$$$的总和不会超过$$$10^6$$$。
输出
对于每个测试,打印 $$$n$$$ 行。第 $$$i$$$ 行包含一个数字,表示该行中第 $$$i$$$ 蚂蚁的生存概率,以 $$$10^9 + 7$$$ 为模。
示例
输入 #1
3 4 5 2
输出 #1
0 250000002 250000002 500000004 0 250000002 250000002 250000002 250000002 0 1
注意
这是 $$$6$$$ 蚂蚁在树枝上移动的示例。蚂蚁的移动将由字符 $$$L$$$ 或 $$$R$$$ 表示。最初,树枝上的蚂蚁群将以 $$$RLRRLR$$$ 移动。以下是该群体的行为表现:
最初,蚂蚁的位置如上。
过了一会儿,索引为$$$2$$$(向左行走)的蚂蚁将与索引为$$$1$$$(向右行走)的蚂蚁发生碰撞。两只蚂蚁的重量相同,因此,蚂蚁 $$$2$$$ 会吃掉蚂蚁 $$$1$$$ 并将其重量增加到 $$$2$$$。同样的事情也发生在 ant $$$5$$$ 和 ant $$$4$$$ 上。
蚂蚁 $$$6$$$ 将走到棍子的末端,从而改变其方向。
之后,索引为 $$$5$$$ 的蚂蚁将与索引为 $$$3$$$ 的蚂蚁一起崩溃。由于蚂蚁$$$5$$$比蚂蚁$$$3$$$重(重量=$$$2$$$)(重量=$$$1$$$),蚂蚁$$$5$$$会吃掉蚂蚁$$$3$$$并将其重量增加到$$$3$$$。
蚂蚁 $$$2$$$ 将走到棍子的末端,因此改变其方向。
之后,索引为 $$$5$$$ 的蚂蚁将与索引为 $$$2$$$ 的蚂蚁一起崩溃。由于蚂蚁$$$5$$$比蚂蚁$$$2$$$重(重量=$$$3$$$)(重量=$$$2$$$),蚂蚁$$$5$$$会吃掉蚂蚁$$$2$$$并将其重量增加到$$$5$$$。
最后,在 ant $$$5$$$ 走到树枝末端并改变方向后,ant $$$5$$$ 将吃掉 ant $$$6$$$ 并成为最后一只站立的蚂蚁。