AT_arc183_f [ARC183F] Sum of Minimum Distance

给定正整数 $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 \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 宋怡芃