题目描述

多组数据，每次给定正整数 $a,b,c,d,e,f,n$，你需要求下式的值：

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

答案对 $10^9+3579$ 取模。

输入格式

第一行一个正整数 $T$ 表示数据组数。

后 $T$ 行，每行七个正整数 $a,b,c,d,e,f,n$ 描述一组询问。

输出格式

$T$ 行，每行回答一组询问，对 $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

提示

本题采用捆绑测试。Subtask 分布如下：

• Subtask 1 (10pts)：$n,T\le 1000$。
• Subtask 2 (20pts)：$c=1$。
• Subtask 3 (70pts)：无特殊限制。

对于全部数据，$1\le T\le 10^5$，$1\le a,b,c,d,e,f,n\le10^9$。

提示：本题输入文件较大，请选手注意 IO 效率。