SP23336 TRNGL - Make Triangle

Chayanika 非常喜欢数学，正在学习一个新的几何章节。在学习中她想到了一个有趣的问题：给定一个具有 $n$ 边的凸多边形，她可以通过画 $(n-3)$ 条不相邻也不相交的对角线将其分割成若干个三角形。那么，有多少种不同的分割方法呢？

输入的第一行为一个整数 $t$（$1 \le t \le 100000$），表示测试用例的数量。接下来的 $t$ 行中，每行包含一个整数 $n$（$3 \le n \le 1000$），表示多边形的边数。

对每个测试用例，输出该多边形可被分割成三角形的方法数，并对结果取模 $100007$。 **本翻译由 AI 自动生成**