**题目描述**

$N$名士兵正在为他们的阅兵式做准备。他们每个人都有不同的高度并且他们站成了一行。他们的指挥官会命令他们中的任何三个人上前（如果不足$3$个人就**不会**下达命令），然后所有其他士兵都会离开，被选择的三个士兵将按原先在队伍中的顺序留下来。现在，如果从左到右，这三个士兵的身高相比较是**矮、高、中等**，那么他们的指挥官就会大发雷霆并惩罚他们。（但如果他们是“中、高、矮”或按从左到右的任何其他顺序，他们不会受到惩罚）。现在士兵们不想受到惩罚。$N$名士兵可以有多少种方式站成一排，无论从左到右选择哪三个顺序永远不会矮、高、中等？

　
 
**输入格式**

输入包含多组数据。第一行输入一个整数$T(1\le T\le500)$，表示数据组数。接下来每行一个整数$N(1\le N\le5000)$，表示士兵人数。

　
 
**输出格式**

对于每组数据，输出一行一个整数，表示有多少种让$N$个士兵站成一排的方法，使士兵们不会受到惩罚。由于答案可能很大，你只需要输出答案对$10^9+7$取模的结果。