3916: 类欧几里得算法
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
这是一道模板题。
给出 $T$ 组询问，每组用 $n, a, b, c, k_1, k_2$ 来描述。对于每组询问，请你求出
$$
\sum_{x = 0} ^ {n} x ^ {k_1} {\left \lfloor \frac{ax + b}{c} \right \rfloor} ^ {k_2}
$$
对 $1000000007$ 取模。
输入
第一行读入一个数 $T$ 。
接下来 $T$ 行，每行读入六个数 $n, a, b, c, k_1, k_2$ 。
输出
输出共 $T$ 行，每行一个答案。
样例输入 复制
1
2 2 0 1 1 1样例输出 复制
10提示
数据范围：对于 $100 \%$ 的数据，$T = 1000, 1 \le n, a, c \le {10} ^ 9, 0\le b\le {10}^9, 0 \le k_1 + k_2 \le 10$ 。 | 子任务 | 分值 | $n$ | $k_1, k_2$ | |:-:|:-:|:-:|:-:| | $1$ | $10$ | $n \le 100000$ | 无特殊限制 | | $2$ | $20$ | 无特殊限制 | $k_1 = 0, k_2 = 1$ | | $3$ | $20$ | 无特殊限制 | $k_1 + k_2 \le 2$ | | $4$ | $50$ | 无特殊限制 | 无特殊限制 |