SP9448 SWARM - Swarm of Polygons

有一个正 $n$ 边形，在它的每条边上标记了一些点。第一条边上标记有 $x_1$ 个点，第二条边上有 $x_2$ 个点，依此类推，第 $n$ 条边上有 $x_n$ 个点。这些点的位置不在正 $n$ 边形的顶点上。从每条边上，你最多可以选择一个标记的点，通过连接这些点来形成一个凸的非退化多边形。你的任务是计算可以形成的不同 $k$ 边形的数量。

输入的第一行是一个整数 $t$，表示测试用例的数量。接下来的 $t$ 行中，每行包含六个整数：$n, k, a, b, c, m$。其中 $n$ 是正 $n$ 边形的边数。第一条边上的标记点数量为 $x_1 = a$，对于之后的边，第 $i$ 条边上的标记点数量为 $x_i = (b \cdot x_{i-1} + c) \mod m$，适用于 $i > 1$ 的情况。

对于每个测试用例，输出一个整数，表示可以形成的 $k$ 边形的数量，并将结果对 1000000007 取模。

- $1 \le t \le 100$ - $3 \le n \le 100$ - $3 \le k \le n$ - $1 \le a, b, c, m \le 10^9$ **本翻译由 AI 自动生成**