J. Random Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Initially, a rooted tree contains only its root, whose depth is $$$1$$$. A child's depth is $$$1$$$ greater than its parent's depth. A vertex without children is a leaf.

In each round, every leaf with depth less than $$$k$$$ independently chooses one action: it adds one child with probability $$$\alpha$$$, adds two children with probability $$$\beta$$$, or adds no children with probability $$$1-\alpha-\beta$$$.

Choices are independent between vertices and between rounds. All participating leaves act simultaneously, and new vertices can first act in the next round. A leaf that adds no children may still participate in later rounds; vertices of depth $$$k$$$ never participate.

Find the expected total number of vertices after $$$n$$$ rounds, including the root, modulo $$$M=998~244~353$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 10000$$$). Description of the test cases follows.

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$0 \le n \le 10^{18}$$$, $$$1 \le k \le 10^6$$$).

The second line contains two numbers $$$\alpha$$$ and $$$\beta$$$ ($$$0 \le \alpha,\beta \le 1$$$, $$$\alpha + \beta \le 1$$$), each with exactly four digits after the decimal point, representing the probabilities of adding one and two children, respectively.

The sum of $$$k$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output one line containing the answer.

Output the expected total number of vertices after $$$n$$$ rounds modulo $$$998~244~353$$$.

Formally, let $$$M = 998~244~353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$z$$$ that $$$0 \le z \lt M$$$ and $$$z \cdot q \equiv p \pmod{M}$$$.

Example
Input
2
2 2
0.2500 0.2500
8 5
0.5000 0.2500
Output
873463811
454218250
Note

In the first test case, $$$\alpha=\beta=1/4$$$ and $$$k=2$$$, so only the root can act. If it adds one or two children in the first round, the final number of vertices is $$$2$$$ or $$$3$$$, respectively. If it adds no children in the first round, it tries to grow again in the second round. Thus the expectation is

$$$$$$\frac14\cdot2+\frac14\cdot3+\frac12\left(\frac14\cdot2+\frac14\cdot3+\frac12\cdot1\right)=\frac{17}{8}$$$$$$.

The modular encoding of $$$\frac{17}{8}$$$ is $$$873463811$$$.