Problem Description

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$.

Input Format

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 Format

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

3
1 2 3 4 5 6 7
7 6 5 4 3 2 1
300 500 700 301 499 720 1000

12
2
477

Hint

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