SP23336 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\le t\le100000$) which is the no of test cases. Each test case contains a single integer $n$ ($3\le n\le1000$) which is the size of the polygon.

For each test case output the no of ways $\bmod\ 100007$.