[MtOI2019] 时间跳跃

就算知道方法，也绝对不能去改变过去，绝不能将存在的可能性转变为既定的现实，未来是没有人能预测的，是无法重来的，正因如此人们才能接受各种痛苦，不幸与飞来横祸，迈步前进。 

因为某些原因，Rintaro 欠了 Mayuri 一根香蕉。 为了封上 Mayuri 的嘴，Rintaro 与 Mayuri 约定，只要 Mayuri 答对这个问题，Mayuri 想要多少香蕉都没问题： --- 机关有 $N$ 条秘密通道，第 $i$ 条秘密通道的长度为 $i$，机关会从 $2^n$ 种选择方式种**等概率**随机选出一些秘密通道，如果选出来的这些秘密通道能组成一个凸多边形，那么这个方案的权值就是选出的秘密通道数量，否则权值为 $0$。 那么请你求出选出来秘密通道的权值的期望模 $10^9+7$ 的值。（两种选择秘密通道的方案不同当且仅当存在一个秘密通道，在一个方案中被选择，而在另一个方案中未被选择。注意，空集也算一个方案。） --- Kurisu：这不就只要... Rintaro：助手你闭嘴！ Mayuri 在纸上画呀画，结果啥也没画出来，于是 Mayuri 就只能找你帮忙了。

输入共 $T+1$ 行。 第一行一个正整数 $T$ 表示有 $T$ 次询问。 接下来 $T$ 行，每行一个正整数表示这一次询问的 $N$。

你的输出应该包含一共 $T$ 行，第 $i$ 行一个非负整数表示询问的期望值模 $10^9+7$ 的值。

5
1
2
3
4
5

0
0
0
937500007
562500005

#### 样例解释 1 容易发现，当 $n$ 小于等于 $3$ 的时候是一定无法组成合法的多边形的。 当 $n=4$ 的时候选出来的边长为这些集合的时候是权值不为 $0$ 的： $\{1,2,3,4\}$，$\{2,3,4\}$。 答案就是 $\frac{7}{16} \equiv 937500007\ (\bmod 1000000007)$ 当 $n=5$ 的时候选出来的边长为这些集合的时候是权值不为 $0$ 的： $\{1,2,3,4\}$，$\{2,3,4\}$，$\{1,2,3,5\}$，$\{2,3,4,5\}$ $\{1,3,4,5\}$，$\{1,2,4,5\}$，$\{2,4,5\}$，$\{3,4,5\}$，$\{1,2,3,4,5\}$。 答案就是 $\frac{34}{32} \equiv 562500005\ (\bmod 1000000007)$ ### 子任务 本题采用捆绑测试。 对于 $100\%$ 的数据，$1\leq n\leq 5000$，$1\leq T \leq 5000$ 本题共 $5$ 个子任务，各子任务的分值和限制如下： 子任务 $1$（$20$分）：$1 \leq n \leq 10$。 子任务 $2$（$30$分）：$1 \leq n \leq 20$。 子任务 $3$（$15$分）：$1 \leq n \leq 50$。 子任务 $4$（$15$分）：$1 \leq n \leq 300$。 子任务 $5$（$20$分）：无特殊限制。 ### 题目来源 [MtOI2019 Extra Round](https://www.luogu.org/contest/22840) T3 出题人：CYJian 验题人：suwAKow