SP6325 NGON - Many polygons

给定一个正 $n$ 边形，在它的每条边上标记了一些点：第一条边标记了 $a_1$ 个点，第二条边标记了 $a_2$ 个点……第 $n$ 条边标记了 $a_n$ 个点。这些标记的点的位置不包含正 $n$ 边形的顶点。你的任务是，使用这些标记点作为顶点，计算可以构成多少个不同的凸的并且是非退化的 $(n-1)$ 边形。

输入的第一行是一个整数 $t$，表示测试用例的数量。接下来的每组测试用例包含两行。第一行是一个整数 $n$，表示原始多边形的边数。第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，分别代表在每条边上标记的点数。

对于每组测试用例，输出可以构建的符合条件的多边形的数量，并对结果取模 $1000000007$。 ## 数据范围 - $1 \le t \le 100$ - $3 \le n \le 10^5$ - $1 \le a_i \le 10^9$ **本翻译由 AI 自动生成**