Ela 去远足

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

Ela 将 $n$ 只蚂蚁从左到右排在一根木棍上。相邻蚂蚁之间的距离、最左边蚂蚁到木棍左端的距离、最右边蚂蚁到木棍右端的距离均相等。每只蚂蚁初始重量均为 $1$，并独立、等概率地选择向左或向右移动；所有蚂蚁速度相同。

蚂蚁到达木棍端点时立即掉头。当两只相向而行的蚂蚁碰撞时：

• 若重量不同，较重的蚂蚁吃掉较轻的蚂蚁，重量变为二者之和，并保持原方向；
• 若重量相同，向左移动的蚂蚁吃掉向右移动的蚂蚁，重量变为二者之和，并继续向左移动。

可以证明，最终恰有一只蚂蚁存活。对每个初始位置 $i$，求该位置的蚂蚁最终存活的概率。

答案对 $M=10^9+7$ 取模。若概率写成最简分数 $p/q$，输出 $p\cdot q^{-1}\bmod M$。

输入格式

第一行一个整数 $t$，表示测试数据组数。

接下来 $t$ 行，每行一个整数 $n$，表示该组实验中的蚂蚁数量。

输出格式

对每组测试，输出 $n$ 行。第 $i$ 行输出初始位置 $i$ 的蚂蚁最终存活的概率模 $10^9+7$ 的值。

样例输入

3
4
5
2

样例输出

0
250000002
250000002
500000004
0
250000002
250000002
250000002
250000002
0
1

数据范围

对所有数据，$1\le t\le 10^3$，$1\le n\le 10^6$，且同一输入文件内所有测试的 $n$ 之和不超过 $10^6$。

每个测试点独立计分。