GLLF 砍木棍
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

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


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


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


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

输入描述:

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

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

输出描述:

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

输入

复制 
5
3
4
5
114514
1919810

输出

复制 
1
1
8
669267460
159473596

备注:

对于第三个测试用例，一种有八种切法：[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]