题目描述

算法竞赛领域有一道关于蚂蚁的经典题，大户爱将其魔改了一下。一个长度为 \(1\) 单位长度的环上有 \(N\) 只蚂蚁，每只蚂蚁的初始位置不会重叠，每只蚂蚁的速度相同且进行匀速圆周运动，均为 \(1\) 单位时间刚好走完一圈。每只蚂蚁初始会等概率随机选择一个方向（逆时针或顺时针）匀速走 \(1\) 单位时间然后停下。任意两只蚂蚁相遇会同时立刻转向。请问每只蚂蚁都能在 \(1\) 单位时间后回到自己的起点的概率。可以证明这个概率仅与每只蚂蚁初始的方向选择有关，与位置无关。 \(N \le 10^7\)。

输入格式

第一行一个整数 \(T\)，表示数据组数。 \(T \le 1000\)。

第二行开始每行一个整数 \(N\)，表示蚂蚁数量。

输出格式

对于每组数据，输出一个整数 \(\text{ans}\)，表示模 \(10^9+7\) 意义下的答案。

样例输入

4
1
2
3
4

样例输出

1
1
250000002
500000004