N. Chapo Nahi Mili
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Anup was working tirelessly to finalize the problem set for the upcoming Insomnia contest. Meanwhile, Darsh, having absolutely nothing better to do, wandered over to demand a treat(chapo in local lingo). Hoping to get back to work, Anup struck a deal: Darsh would get his chapo, but only if he could first solve a seemingly innocent, yet "not-so-simple" problem.

Anup describes a process to build a tree:

Given an integer $$$n$$$, construct an array $$$a[a_1,a_2,\ldots,a_n]$$$ of size $$$n$$$ consisting of zeroes and ones where $$$a_1= 0 $$$. Consider a tree with $$$n+1$$$ vertices labeled $$$0, 1, 2, \ldots, n$$$, where vertex $$$0$$$ is designated as the root.

For each $$$i = 1, 2, 3, \ldots, n$$$, if:

  • $$$a_i = 0$$$, add an edge between vertex $$$i$$$ and vertex $$$i-1$$$;
  • $$$a_i = 1$$$, add an edge between vertex $$$i$$$ and vertex $$$i-2$$$.

Let $$$h(a)$$$ be the height of the tree for one possible valid array $$$a$$$. Anup asks Darsh to find the sum of $$$h(a)$$$ over all possible valid arrays of $$$0$$$s and $$$1$$$s where $$$a_1 = 0$$$. Since this sum can be incredibly large, output the answer modulo $$$10^9 + 7$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the size of the array.

Output

For each test case, output a single integer — the sum of the heights of the trees formed by all valid arrays, modulo $$$10^9 + 7$$$.

Example
Input
2
1
2
Output
1
3