← 返回题目列表

AtCoder · arc183_f

F. 最小距离之和

中文机器翻译题面 查看原题

分数: 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.