F - Sum of Minimum Distance

F - Sum of Minimum Distance 解説

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 1100 点

正整数 A,B,X,Y,N が与えられます．ここで，以下が保証されます．

整数 n に対し，f(n) を以下のように定義します．

整数 x=0 を持った状態からスタートし，以下の操作を繰り返して x=n を達成するのにかかるコストの合計の最小値を f(n) とする．
- x の値を x+A で置き換える．コストが X かかる．
- x の値を x-A で置き換える．コストが X かかる．
- x の値を x+B で置き換える．コストが Y かかる．
- x の値を x-B で置き換える．コストが Y かかる．

なお，A,B の制約より，任意の整数 n に対して f(n) が定義できることが証明できます．

\sum_{1 \leq n \leq N} f(n) の値を 998244353 で割ったあまりを求めてください．

1 つの入力につきテストケースは T 個あります．

入力は標準入力から以下の形式で与えられる。

T
case_1
case_2
\vdots
case_T

各テストケースは以下の形式で与えられる。

A B X Y N

各テストケースに対して答えを出力せよ．

4
1 2 1 1 2
3 5 2 4 6
79 85 72 95 4
80980429 110892168 22712439 520643153 66132787

1 つめのテストケースでは，f(1)=1,f(2)=1 です．

2 つめのテストケースでは，f(1)=8,f(2)=6,f(3)=2,f(4)=10,f(5)=4,f(6)=4 です．

Score : 1100 points

You are given positive integers A, B, X, Y, and N. Here, the following is guaranteed:

For an integer n, define f(n) as follows:

You start with an integer x=0. f(n) is the minimum total cost to achieve x=n by repeatedly performing the following operations.
- Replace the value of x with x+A. The cost of this operation is X.
- Replace the value of x with x-A. The cost of this operation is X.
- Replace the value of x with x+B. The cost of this operation is Y.
- Replace the value of x with x-B. The cost of this operation is Y.

It can be proved from the constraints on A and B that f(n) is defined for any integer n.

Find the value of \sum_{1 \leq n \leq N} f(n), modulo 998244353.

There are T test cases for each input.

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each test case is given in the following format:

A B X Y N

Print the answer for each test case.

4
1 2 1 1 2
3 5 2 4 6
79 85 72 95 4
80980429 110892168 22712439 520643153 66132787

In the first test case, f(1)=1 and f(2)=1.

In the second test case, f(1)=8, f(2)=6, f(3)=2, f(4)=10, f(5)=4, and f(6)=4.