#138. 类欧几里得算法

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

题目描述

这是一道模板题。

给出 TT 组询问,每组用 n,a,b,c,k1,k2n, a, b, c, k_1, k_2 来描述。对于每组询问,请你求出

x=0nxk1ax+bck2 \sum_{x = 0} ^ {n} x ^ {k_1} {\left \lfloor \frac{ax + b}{c} \right \rfloor} ^ {k_2}

10000000071000000007 取模。

输入格式

第一行读入一个数 TT

接下来 TT 行,每行读入六个数 n,a,b,c,k1,k2n, a, b, c, k_1, k_2

输出格式

输出共 TT 行,每行一个答案。

样例

样例输入

1
2 2 0 1 1 1

样例输出

10

数据范围与提示

对于 100%100 \% 的数据,T=1000,1n,a,b,c109,0k1+k210T = 1000, 1 \le n, a, b, c \le {10} ^ 9, 0 \le k_1 + k_2 \le 10

子任务 分值 nn k1,k2k_1, k_2
11 1010 n100000n \le 100000 无特殊限制
22 2020 无特殊限制 k1=0,k2=1k_1 = 0, k_2 = 1
33 2020 无特殊限制 k1+k22k_1 + k_2 \le 2
44 5050 无特殊限制 无特殊限制