M. GLLF 砍木棍
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

上回 GLLF 对一个木头砍了 $$$10^{100}$$$ 刀，他感觉有点累了，所以他决定砍一根木棍。

他有一根长度为正整数 $$$n$$$ 的木棍，把它砍成了若干个长度为正整数的小段，他很好奇有多少种砍法能使得这些小段木棍能拼成一个凸多边形。

两种砍法不同当且仅当存在砍的位置不同。我们把每段的长度按顺序放入数组，如长度为 $$$6$$$ 的木棍按顺序砍出 $$$1,2,1,2$$$ 四段，则可以表示为 $$$[1,2,1,2]$$$。两个不同的数组代表不同的砍法。

由于这个问题的答案可能很大，请你将答案对 $$$10^9 + 7$$$ 取模之后输出。

Input

第一行一个正整数 $$$T$$$ ($$$1 \le T \le 10^5$$$)，表示数据组数。

接下来 $$$T$$$ 行，每行一个正整数 $$$n$$$ ($$$3\le n \le 10^9$$$)，表示木棍的长度。

Output

对于每组数据，输出一行一个对 $$$10^9 + 7$$$ 取模之后的整数，表示有多少种砍法。

Example
Input
5
3
4
5
114514
1919810
Output
1
1
8
669267460
159473596
Note

对于第三个测试用例，一种有八种切法：$$$[1,1,1,1,1]$$$, $$$[1,1,1,2]$$$, $$$[1,1,2,1]$$$, $$$[1,2,1,1]$$$, $$$[2,1,1,1]$$$, $$$[1, 2, 2]$$$, $$$[2, 1, 2]$$$, $$$[2, 2, 1]$$$