#138. 类欧几里得算法

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Sdchr

题目描述

这是一道模板题。

给出 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, b, c \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 无特殊限制