Problem Statement

There are $N$ cards arranged face down in a row, each with one of the integers $1,2,\dots,N$ written on its face. The order of these cards is determined uniformly at random from the $N!$ possible orders. You know that there is exactly one card with each of the integers $1,2,\dots,N$ written on its face and that the cards were arranged uniformly at random, but you have no other information about the integers written on the faces of the cards.

You play the following game.

• Initially, let the variable $x=1$.
• As long as $x \le N$, repeat the following operation. One operation consists of the following three steps.
• Specify one card and turn it face up.
• If the integer written on the card is $x$, eat that card and add $1$ to $x$.
• Otherwise, turn that card face down. You can permanently remember the integer written on that card.

You always act so that the expected value of the total number of operations until all cards have been eaten is minimized. In this case, what is the probability that the total number of operations is $K$? Find it modulo $998244353$.

Definition of probability modulo $998244353$

It can be proved that the sought probability is always a rational number. Also, under the constraints of this problem, it can be proved that when the rational number to be found is expressed as an irreducible fraction $\frac{P}{Q}$, we have $Q {{}\not\equiv{}} 0 \pmod{998244353}$. Therefore, there is a unique integer $R$ satisfying $R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353$. Output this $R$.

Constraints

• All input values are integers.
• $1 \le N \le 5 \times 10^5$
• $N \le K \le 10^9$

Input

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

• $N$ $K$

Output

Output the answer.

3 4

499122177

For this input, $N=3$. Let us call the cards $a,b,c$ in the order they are arranged. Below is an example of your actions when acting so that the expected value of the total number of operations is minimized.

• First, turn $a$ face up.
  • If $1$ is written on $a$, eat that card.
    • Next, turn $b$ face up.
      • If $2$ is written on $b$, eat that card.
        • Next, turn $c$ face up; since $3$ is necessarily written on it, eat it. In this case, you eat all cards in three operations, and the probability of this happening is $1/6$.
      • If $3$ is written on $b$, turn that card face down.
        • Next, turn $c$ face up; since $2$ is necessarily written on it, eat it. After that, turn $b$ face up and eat it. In this case, you eat all cards in four operations, and the probability of this happening is $1/6$.
  • If $2$ is written on $a$, turn that card face down.
    • Next, turn $b$ face up.
      • If $1$ is written on $b$, eat that card.
        • Next, turn $a$ face up and eat it. Next, turn $c$ face up; since $3$ is necessarily written on it, eat it. In this case, you eat all cards in four operations, and the probability of this happening is $1/6$.
      • If $3$ is written on $b$, turn that card face down.
        • At this point, it has become clear which integer is written on every one of the cards. So, perform three operations and eat all the cards in order of their numbers. In this case, you eat all cards in five operations, and the probability of this happening is $1/6$.
  • If $3$ is written on $a$, turn that card face down.
    • Next, turn $b$ face up.
      • If $1$ is written on $b$, eat that card.
        • Next, turn $c$ face up; since $2$ is necessarily written on it, eat it. After that, turn $a$ face up and eat it. In this case, you eat all cards in four operations, and the probability of this happening is $1/6$.
      • If $2$ is written on $b$, turn that card face down.
        • At this point, it has become clear which integer is written on every one of the cards. So, perform three operations and eat all the cards in order of their numbers. In this case, you eat all cards in five operations, and the probability of this happening is $1/6$.

Combining everything, the probability that the total number of operations is $3$ is $1/6$, the probability that it is $4$ is $1/2$, and the probability that it is $5$ is $1/3$. For this sample, output $499122177$, which represents $1/2$ modulo $998244353$.

3 6

0

500000 777777

251612105

• Source: AtCoder ABC 473 G