CF1369D TediousLee

首先，我们定义 `RDB` 为一棵具有特殊性质的树，它有一个级别 $level$。 一个级别为 $1$ 的 `RDB` 是一个单独的节点。 接着，对于所有 $i>1$，级别为 $i$ 的 `RDB` 的构成方法如下。 先求出级别为 $i-1$ 的 `RDB`，然后对于该 `RDB` 中的每个节点 $x$。 - 如果 $x$ 没有孩子，那么给他加上一个孩子。 - 如果 $x$ 只有一个孩子，那么给他加上两个孩子。 - 如果 $x$ 已经有了超过一个孩子，那么我们跳过节点 $x$。 以下是 $1\le n \le 3$ 的所有 `RDB`  接下来，我们定义一个 `claw` （见下图），它也是一棵具有特殊性质的树，并且将节点 $1$ 称为这个 `claw` 的中心，其他的称为底部节点。  现在，给出一个级别为 $n$ 的 `RDB`，初始时他上面的所有节点都为绿色，你可以进行一些操作。 对于每次操作，你需要在给出的 `RDB` 中找到一个 `claw`，满足所有底部节点在 `RDB` 中都是中心节点的儿子，且这四个节点在 `RDB` 中都是绿色。然后将这四个节点染为黄色。 问最多可以将多少个节点染成黄色。

第一行一个整数 $T$，表示数据的组数。 接下来 $T$ 行，每行一个正整数 $n$，表示有一棵级别为 $n$ 的 `RDB`。

输出有 $n$ 行，每行一个整数，对应每组数据的答案。 这个答案可能很大，所以输出它对 $10^9+7$ 取模后的结果。

### 提示 很容易看出，$1$ 级或 $2$ 级 RDB 的答案是 $0$。 $3$ 级 RDB 的答案是 $4$，因为只有一个可选的结构：$\{1, 2, 3, 4\}$。 $4$ 级 RDB 的答案是 $4$，因为我们可以选择单个结构 $\{1, 3, 2, 4\}$ 或单个结构 $\{2, 7, 5, 6\}$。$4$ 级 RDB 中没有其他结构（例如，我们不能选择 $\{2, 1, 7, 6\}$，因为 $1$ 不是中心顶点 $2$ 的子节点）。  ### 数据范围 $1\le T\le 10^4$ $1\le n \le 2\cdot 10^6$ 感谢 @[_Wolverine](https://www.luogu.com.cn/user/120362) 提供的翻译