409019: GYM103415 K Magus Night

Marisa Kirisame has been collecting Supernatural Beads. Now she has got $$$n$$$ Beads, and she wants to use them to perform her representative magic, Master Spark.

When she prepares to perform magic, the Beads will be energized. Formally, each of the Beads will get an integer in $$$[1,m]$$$ as its energy, completely randomly and independently. Note that the energy of a Bead may change when she repeats energizing.

After some practising, she finds a few interesting facts about her Beads. Assume that the energy of the Beads is $$$s_1, s_2, \ldots, s_n$$$, then the power of the magic is $$$\operatorname{lcm}(s_1, s_2, \ldots, s_n)$$$, and the cost of the magic is $$$\gcd(s_1, s_2, \ldots, s_n)$$$. Here $$$\operatorname{lcm}(s_1, s_2, \ldots, s_n)$$$ denotes the Least Common Multiple (LCM) of integers $$$s_1, s_2, \ldots, s_n$$$, and $$$\gcd(s_1, s_2, \ldots, s_n)$$$ denotes the Greatest Common Divisor (GCD) of integers $$$s_1, s_2, \ldots, s_n$$$.

Marisa is strict about magic. She sets two positive integers $$$p$$$ and $$$q$$$ no greater than $$$m$$$, and she regards a magic successful if and only if the power of the magic is no less than $$$p$$$ and the cost of the magic is no greater than $$$q$$$. She thinks the value of a magic is $$$\prod_{i=1}^n s_i$$$ if the magic is successful, and $$$0$$$ otherwise.

Now she wonders about the expected value of magic. Let the answer be $$$x$$$, it is obvious that $$$x\cdot m^n$$$ is an integer. As this number may be large, you only need to tell her $$$x\cdot m^n \bmod 998244353$$$.

The only line of the input contains four integers, $$$n$$$, $$$m$$$, $$$p$$$, and $$$q$$$ — the number of the Beads, the maximum possible energy of the Beads and the two parameters on defining successful magics.

It is guaranteed that $$$1\leq n \leq 998244351$$$ and $$$1\leq p, q\leq m\leq 2\times 10^5$$$.

The only line of the output contains a single integer in $$$[0, 998244353)$$$ — the expected value of a magic, that is, $$$x\cdot m^n$$$ in the last paragraph of the statement.

2 4 3 2

66

7 2 1 2

2187

In the first example, there are $$$16$$$ possible situations, and the successful ones are listed below:

$$$\{1, 3\}$$$, $$$\{1, 4\}$$$, $$$\{2, 3\}$$$, $$$\{2, 4\}$$$, $$$\{3, 1\}$$$, $$$\{3, 2\}$$$, $$$\{3, 4\}$$$, $$$\{4, 1\}$$$, $$$\{4, 2\}$$$, $$$\{4, 3\}$$$.

Those situations are not successful, for their power is less than $$$3$$$:

$$$\{1, 1\}$$$, $$$\{1, 2\}$$$, $$$\{2, 1\}$$$, $$$\{2, 2\}$$$.

Those situations are not successful, for their cost is more than $$$2$$$:

$$$\{3, 3\}$$$, $$$\{4, 4\}$$$.

In the second example, it is obvious that all $$$2^7$$$ situations are successful.