分数: 1100 点
问题陈述
给你正整数 A, B, X, Y,和 N。 在此,保证如下:
- A<B
- \gcd(A,B)=1
- 1 \leq N \leq A+B-1
对于整数 n,定义 f(n) 如下:
- 你以一个整数开始 x=0. f(n) 是实现的最低总成本 x=n 通过重复执行以下操作。
- 替换值 在此过程中的任何时刻都必须保持 x 与 x+A。该操作的成本是 X.
- 替换值 在此过程中的任何时刻都必须保持 x 与 x-A。该操作的成本是 X.
- 替换值 在此过程中的任何时刻都必须保持 x 与 x+B。该操作的成本是 Y.
- 替换值 在此过程中的任何时刻都必须保持 x 与 x-B。该操作的成本是 Y.
从约束条件可以证明 A 和 B 那 f(n) 被定义为任何整数 n.
查找值 \sum_{1 \leq n \leq N} f(n),模数 998244353.
有 T 每个输入的测试用例。
约束
- 1 \leq T \leq 1000
- 1 \leq A<B \leq 10^9
- \gcd(A,B)=1
- 1 \leq X,Y \leq 10^9
- 1 \leq N \leq A+B-1
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T case_1 case_2 \vdots case_T
每个测试用例均按以下格式给出:
A B X Y N
输出
打印每个测试用例的答案。
示例输入 1
4 1 2 1 1 2 3 5 2 4 6 79 85 72 95 4 80980429 110892168 22712439 520643153 66132787
示例输出 1
2 34 18111 785776602
在第一个测试用例中, f(1)=1 和 f(2)=1.
在第二个测试用例中, f(1)=8, f(2)=6, f(3)=2, f(4)=10, f(5)=4,和 f(6)=4.