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\le T\le 10^4$ $1\le n \le 2\cdot 10^6$ 感谢 @[_Wolverine](https://www.luogu.com.cn/user/120362) 提供的翻译

题目描述

Lee tried so hard to make a good div.2 D problem to balance his recent contest, but it still doesn't feel good at all. Lee invented it so tediously slow that he managed to develop a phobia about div.2 D problem setting instead. And now he is hiding behind the bushes... Let's define a Rooted Dead Bush (RDB) of level $ n $ as a rooted tree constructed as described below. A rooted dead bush of level $ 1 $ is a single vertex. To construct an RDB of level $ i $ we, at first, construct an RDB of level $ i-1 $ , then for each vertex $ u $ : - if $ u $ has no children then we will add a single child to it; - if $ u $ has one child then we will add two children to it; - if $ u $ has more than one child, then we will skip it. Rooted Dead Bushes of level $ 1 $ , $ 2 $ and $ 3 $ . Let's define a claw as a rooted tree with four vertices: one root vertex (called also as center) with three children. It looks like a claw: The center of the claw is the vertex with label $ 1 $ . Lee has a Rooted Dead Bush of level $ n $ . Initially, all vertices of his RDB are green. In one move, he can choose a claw in his RDB, if all vertices in the claw are green and all vertices of the claw are children of its center, then he colors the claw's vertices in yellow. He'd like to know the maximum number of yellow vertices he can achieve. Since the answer might be very large, print it modulo $ 10^9+7 $ .

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Next $ t $ lines contain test cases — one per line. The first line of each test case contains one integer $ n $ ( $ 1 \le n \le 2 \cdot 10^6 $ ) — the level of Lee's RDB.

输出格式

For each test case, print a single integer — the maximum number of yellow vertices Lee can make modulo $ 10^9 + 7 $ .

输入输出样例

输入样例 #1

7
1
2
3
4
5
100
2000000

输出样例 #1

0
0
4
4
12
990998587
804665184

说明

It's easy to see that the answer for RDB of level $ 1 $ or $ 2 $ is $ 0 $ . The answer for RDB of level $ 3 $ is $ 4 $ since there is only one claw we can choose: $ \{1, 2, 3, 4\} $ . The answer for RDB of level $ 4 $ is $ 4 $ since we can choose either single claw $ \{1, 3, 2, 4\} $ or single claw $ \{2, 7, 5, 6\} $ . There are no other claws in the RDB of level $ 4 $ (for example, we can't choose $ \{2, 1, 7, 6\} $ , since $ 1 $ is not a child of center vertex $ 2 $ ). Rooted Dead Bush of level 4.