I I U P C 2 0 1 4
Problem A: The Soldier’s Dilemma
N soldiers are preparing for their parade. Each of them has different heights and they are standing in a line. Their commander will order any three of them to step forward. All the other soldiers will then leave the ground and selected three will stay. Now if from left to right these three soldier’s order is short, tall, medium then their commander will become furious and punish them.(Even if they are “medium, tall, short” or in any other order from left to right they will not be punished) Now the soldiers don’t want to be punished. In how many ways can the N soldiers stand in a line that no matter which three are chosen there order will never be short, tall , medium from left to right?
Input
The first line contains number of test case T (1≤T≤500). Each of the next T lines contains an integer N (1≤N≤5000).
Output
For each of the test case you must output the number of ways N soldiers can stand in a line. As the number can be very large output it modulo 1000000007 (10^9+7).
Sample Input	Output for Sample Input
2 2 3	2 5
Problem Setter: Sakib Shafayat