Description

因为某些原因，Rintaro 欠了 Mayuri 一根香蕉。

为了封上 Mayuri 的嘴，Rintaro 与 Mayuri 约定，只要 Mayuri 答对这个问题，Mayuri 想要多少香蕉都没问题：

机关有 $N$ 条秘密通道，第 $i$ 条秘密通道的长度为 $i$，机关会从 $2^n$ 种选择方式种等概率随机选出一些秘密通道，如果选出来的这些秘密通道能组成一个凸多边形，那么这个方案的权值就是选出的秘密通道数量，否则权值为 $0$。

那么请你求出选出来秘密通道的权值的期望模 $10^9+7$ 的值。（两种选择秘密通道的方案不同当且仅当存在一个秘密通道，在一个方案中被选择，而在另一个方案中未被选择。注意，空集也算一个方案。）

Kurisu：这不就只要...

Rintaro：助手你闭嘴！

Mayuri 在纸上画呀画，结果啥也没画出来，于是 Mayuri 就只能找你帮忙了。

Input Format

输入共 $T+1$ 行。

第一行一个正整数 $T$ 表示有 $T$ 次询问。

接下来 $T$ 行，每行一个正整数表示这一次询问的 $N$。

Output Format

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

5
1
2
3
4
5

0
0
0
937500007
562500005

Hint

样例解释 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 T3

出题人：CYJian

验题人：suwAKow