TRNGL  Make Triangle
Chayanika loves Mathematics. She is learning a new chapter geometry. While reading the chapter a question came in her mind. Given a convex polygon of n sides. In how many ways she can break it into triangles, by cutting it with (n3) nonadjacent diagonals and the diagonals do not intersect.
Input
First line of the input will be an integer t (1<=t<=100000) which is the no of test cases. Each test case contains a single integer n (3<=n<=1000) which is the size of the polygon.
Output
For each test case output the no of ways %100007.
Example
Input: 2
3
5
Output: 1
5
hide comments
nadstratosfer:
20171012 15:46:56
natsu: Draw a pentagon, denoting its corners 1,2,3,4,5. You can draw 2 diagonals in a V shape between these 5 combs of corners: 135, 253, 314, 142, 524. 

Ankush :
20150621 09:02:35
It's a well know sequence :P Though implementation wasn't easy. Costed 4 TLEs in Python. Finally did it in Python 2.7.9 :D Last edit: 20150621 09:03:45 

Hiesenberg:
20150329 21:42:21
@ashish for n=7 output = 42


natsu:
20150329 12:58:12
How the output is 5 for n=5(pentagon) in second test case?


ashish jaiswal:
20150328 14:45:31
can i know the output for n=7? 
Added by:  Aadil Ahmad 
Date:  20150320 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 JSMONKEY 