Another Coin Weighing Puzzle

You have some bags of coins. Each bag contains exactly $k$ coins. Exactly one bag contains only counterfeit coins (we will call it the fake bag), and every other bag contains only real coins. All real coins weigh exactly the same number of grams. All counterfeit coins weigh exactly the same number of grams. You do not know the exact weights of a real or a counterfeit coin. You do know that a counterfeit coin is strictly heavier than a real coin, but you do not know exactly how much heavier it is. The weights of the coins are positive real numbers.

You have a scale that you can use at most $m$ times. The scale has a left side and a right side. To use the scale, you can place any number of coins, taken from any of the bags, on each side, as long as the total numbers of coins on the left and right sides are exactly equal. The scale returns a single real number $s$. If $s$ is zero, both sides weigh exactly the same. If $s$ is negative, the left side is $|s|$ grams heavier than the right side. If $s$ is positive, the right side is $s$ grams heavier than the left side. Coins can be reused across different weighings, and you can keep track of which bag each coin came from. You must specify beforehand all the weighings you want to perform, so you cannot adjust what gets weighed later based on the results of earlier weighings. After using the scale $m$ times, you want to determine which bag is the fake bag.

You are now wondering: given $m$ and $k$, what is the maximum number of bags for which you can always determine the fake bag? This number can get large, so output it modulo the large prime 998,244,353.

The single line of input contains two space-separated integers $m$ and $k$ ($1 \le m, k \le 10^6$), where $m$ is the number of weighings available to you and $k$ is the number of coins in each bag.

Output a single integer, the maximum number of bags for which you can determine the fake bag in $m$ weighings, modulo the large prime 998,244,353.

One way to use 2 weighings to determine the fake bag among 9 bags, each containing 1 coin, is as follows:

• On the first weighing, put the coins from bags 1, 2, 3 on the left, and the coins from bags 7, 8, 9 on the right.
• On the second weighing, put the coins from bags 1, 4, 7 on the left, and the coins from bags 3, 6, 9 on the right.

We can determine the fake bag as follows:

• The first weighing tells us which group of bags, (1, 2, 3), (4, 5, 6), or (7, 8, 9), contains the fake bag (for example, if the left side is heavier, then group (1, 2, 3) contains the fake bag; if both sides are equal, then group (4, 5, 6) does; otherwise group (7, 8, 9) does).
• The second weighing tells us which group of bags, (1, 4, 7), (2, 5, 8), or (3, 6, 9), contains the fake bag. The fake bag is then determined uniquely.