[AdditionalFile138.zip](file://AdditionalFile138.zip?type=additional_file)

#138. 类欧几里得算法

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB | 显示标签 通过: 519 | 提交: 1068

题目描述

这是一道模板题。

给出 $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			$k_1 + k_2 \le 2$
4	50		无特殊限制