题目描述

给定整数 $N, M, A, B, X, R$。

求 $\displaystyle \sum_{k=0}^{N-1} X^{(Ak+B) \bmod M}$ 被 $R$ 除后的余数。

给定 $T$ 组测试数据，请分别输出每组的答案。

输入格式

输入通过标准输入给出，格式如下：

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

每组测试数据 $\text{case}_i$ 的格式为：

$N\ M\ A\ B\ X\ R$

输出格式

输出 $T$ 行。

第 $i$ 行输出第 $i$ 组测试数据下 $\displaystyle \sum_{k=0}^{N-1} X^{(Ak+B)\bmod M}$ 被 $R$ 除后的余数。

输入输出样例 #1

输入 #1

3
4 5 2 1 2 1000000000
777 429 33 58 1 1000000000
20251025 429429 777 1025 575757 998244353

输出 #1

15
777
445271630

说明/提示

样例解释 1

考虑第一组测试数据。

• 当 $k=0$ 时：$X^{(Ak+B)\bmod M}=2^{(2\times 0+1)\bmod 5}=2^1=2$。
• 当 $k=1$ 时：$X^{(2\times 1+1)\bmod 5}=2^3=8$。
• 当 $k=2$ 时：$X^{(2\times 2+1)\bmod 5}=2^0=1$。
• 当 $k=3$ 时：$X^{(2\times 3+1)\bmod 5}=2^2=4$。

由上可知，所需的值是 $2+8+1+4$ 被 $1000000000$ 除后的余数，即 $15$。因此，第 $1$ 行输出 $15$。

数据范围

• $1\le T\le 100$
• $1\le N,M,R\le 10^9$
• $0\le A,B < M$
• $1\le X < R$
• 所有输入均为整数。

由 ChatGPT 5 翻译