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 (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?
|
|
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 |