#1581. 类欧几里得算法

类欧几里得算法

题目描述

这是一道模板题。

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

$$\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, 1 \le n, a, c \le {10} ^ 9, 0\le b\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 无特殊限制