P17239 "STA - R10" Rain Falls on Roses

This is a multi-test problem. Each test gives positive integers $a, b, c, d, e, f, n$. You need to compute the following value: $$\sum_{x=1}^n\left[\left\lfloor\dfrac{ax+b}c\right\rfloor\le\left\lfloor\dfrac{dx+e}f\right\rfloor\right]\cdot\left\lfloor\dfrac{ax+b}c\right\rfloor$$ Take the answer modulo $10^9+3579$.

The first line contains a positive integer $T$, the number of test cases. The next $T$ lines each contain seven positive integers $a, b, c, d, e, f, n$, describing one query.

Output $T$ lines. Each line is the answer for one query, modulo $10^9+3579$.

**This problem uses bundled tests.** Subtasks are as follows: - Subtask 1 (10 pts): $n, T \le 1000$. - Subtask 2 (20 pts): $c = 1$. - Subtask 3 (70 pts): No special constraints. Constraints for all testdata: $1 \le T \le 10^5$, $1 \le a, b, c, d, e, f, n \le 10^9$. Note: The input file is large, so please pay attention to I/O efficiency. Translated by ChatGPT 5