题目描述

给定正整数 $A, B, X, Y, N$，其中保证以下条件：

• $A < B$
• $\gcd(A,B) = 1$
• $1 \leq N \leq A+B-1$

定义一个函数 $f(n)$ 如下：

• 从整数 $x=0$ 开始，通过以下操作之一，达到 $x=n$ 所需的最小代价为 $f(n)$：
  • 用 $x+A$ 替换当前的 $x$，此操作花费 $X$。
  • 用 $x-A$ 替换当前的 $x$，此操作花费 $X$。
  • 用 $x+B$ 替换当前的 $x$，此操作花费 $Y$。
  • 用 $x-B$ 替换当前的 $x$，此操作花费 $Y$。

由于 $A, B$ 的约束，可以证明对于任意整数 $n$，$f(n)$ 都可以被定义。

现在需要计算 $\sum_{1 \leq n \leq N} f(n)$ 的值，并对 $998244353$ 取模。

每个输入包含多个测试用例。

输入格式

输入从标准输入中给出，格式如下：

$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

输出

2
34
18111
785776602

说明/提示

约束

• $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$
• 所有输入的值均为整数。

样例解释

对于第一个测试用例，$f(1)=1,f(2)=1$。 对于第二个测试用例，$f(1)=8,f(2)=6,f(3)=2,f(4)=10,f(5)=4,f(6)=4$。

Translate by 宋怡芃