SP5977 WEIRDFN - Weird Function

给定如下序列定义： - $F[1] = 1$ - 对于 $i > 1$，$F[i]$ 的计算公式为：$F[i] = (a \times M[i] + b \times i + c) \mod 1000000007$ 其中，$M[i]$ 是数组 $\{F[1], F[2], \ldots, F[i-1]\}$ 的中位数。中位数在数组排序后是位于中间的元素。如果数组元素个数是偶数，则取中间两个元素中靠前的一个作为中位数。 现在，给定整数 $a$、$b$、$c$ 和 $n$，需要计算序列从 $F[1]$ 到 $F[n]$ 的和。

第一行输入一个整数 $T$，表示测试用例的数量。接下来有 $T$ 行，每行包含四个整数：$a$、$b$、$c$ 和 $n$，分别表示题目中的参数。

对于每个测试用例，输出一行结果，即所求的和。 ## 数据范围 - $1 \le T \le 10^5$ - $0 \le a, b, c < 1000000007$ - $1 \le n \le 10^5$ **本翻译由 AI 自动生成**