TRNGL - Make Triangle

no tags 

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 (n-3) non-adjacent diagonals and the diagonals do not intersect.

Input

First line of the input will be an integer t (1<=t<=100000) which is the number 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: 2017-10-12 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: 1-3-5, 2-5-3, 3-1-4, 1-4-2, 5-2-4.

Ankush : 2015-06-21 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: 2015-06-21 09:03:45
Hiesenberg: 2015-03-29 21:42:21

@ashish for n=7 output = 42

natsu: 2015-03-29 12:58:12

How the output is 5 for n=5(pentagon) in second test case?
It should be 3 as non-intersecting diagonals given.Can anyone please explain.

ashish jaiswal: 2015-03-28 14:45:31

can i know the output for n=7?


Added by:Aadil Ahmad
Date:2015-03-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY