J. Arknights Chips
time limit per test
7 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Note that since the online judge runs a little faster than codeforces, the time limit here is 7 seconds as opposed to 5 seconds.

Waymo has been farming chips from the sniper-caster chip stage. The stage has a $$$p$$$ chance of dropping a sniper chip and a $$$1 - p$$$ chance of dropping a caster chip. Waymo only has use for sniper chips, and he can exchange exactly $$$x$$$ caster chips for exactly $$$y$$$ sniper chips (Waymo can exchange as many times as he wants provided he still has at least $$$x$$$ caster chips). Waymo only has the sanity to play the stage $$$n$$$ times. What is the expected number of sniper chips he can obtain?

Input

The first line of input contains a single integer $$$T$$$, denoting the number of test cases $$$(1 \leq T \leq 20)$$$.

The first line of each test case contains four integers $$$a \ x \ y \ n$$$, denoting $$$p = \frac{a}{100}$$$, $$$x$$$ and $$$y$$$ as the caster to sniper chip conversion, and n as the number of times Waymo plays the stage $$$(0 \leq a \leq 100, 1 \leq y \leq x \leq 100, 1 \leq n \leq 10^{18})$$$.

—

Test in subtasks are numbered $$$1 \dots 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.

For all odd tests, $$$a = 50$$$.

For tests $$$1 - 2$$$, $$$x, y, n \leq 8$$$.

For tests $$$3 - 6$$$, the sum of $$$n$$$ across all test cases is $$$\leq 10^5$$$.

There are no additional constraints on the remaining tests.

Output

For each test case, output one integer $$$E$$$, where $$$E$$$ is the expected number of sniper chips modulo $$$998244353$$$. Let the expected number of sniper chips be $$$\frac{s}{t}$$$, output $$$E$$$ where $$$E \cdot t \equiv s \pmod {998244353}$$$.

Examples
Input
4
50 3 2 3
50 3 2 5
9 8 7 6
25 7 6 2
Output
249561090
499122180
818560370
499122177
Input
3
33 36 33 3366
10 50 30 100000
23 47 26 123456789
Output
872335076
227994141
125109249
Note

Say a sniper chip is $$$a$$$ and a caster chip is $$$b$$$.

The first test case's expected value is as follows:

$$$aaa=3, aab=2, aba=2, abb=1, baa=2, bab=1, bba=1, bbb=2$$$

Each scenario is equally likely to occur.

$$$\frac{3 + 2 + 2 + 1 + 2 + 1 + 1 + 2}{8} = \frac{14}{8}$$$

$$$\frac{14}{8} \equiv 249561090 \pmod{998244353}$$$

For the second test case, $$$\frac{112}{32} \equiv 499122180 \pmod{998244353}$$$

—

Problem Idea: 3366

Problem Preparation: 3366

Occurrences: Advanced 10