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.
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.
For each test case output the no of ways %100007.
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.
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 :DLast edit: 2015-06-21 09:03:45
@ashish for n=7 output = 42
How the output is 5 for n=5(pentagon) in second test case?
can i know the output for n=7?