Under construction

Still being built. Things may change

Blind Box

Time limit1sMemory limit512 MB

Summary
Given n and m, find the average product over all non-decreasing boxes of n cards with values up to m, as a fraction modulo 998244353.
Level

Medium7 of 10

Topics
Combinatorics, Math, Number theory
Solved
No attempts yet

Problem

You are the owner of a store.

The store has launched a new blind box campaign. Each blind box contains nn cards, and there is a positive integer written on each card. The cards in each box are ordered so that the number on the ii-th card is greater than or equal to the number on the (i−1)(i{-}1)-th card for every i>1i > 1. The integer on each card does not exceed mm.

The store has all possible blind boxes satisfying these conditions, and no two boxes in the store are the same. Two boxes are different if and only if there is an index ii such that the numbers on the ii-th cards of the two boxes differ.

You sell blind boxes at a fixed price. After a customer buys and opens a box, they ask you for a cashback equal to the product of the numbers on the nn cards in the box. Find the minimum price of each blind box such that your net income is non-negative after all boxes are sold.

Input

The first line contains two integers nn and mm: the number of cards in each box and the maximum value on a card (1≤n,m≤1051 \leq n, m \leq 10^5).

Output

Print a single integer: the minimum price, modulo 998 244 353998\,244\,353. The price may be a fraction. If the minimum price is the irreducible fraction xy\frac{x}{y}, print x⋅y−1 mod 998 244 353x \cdot y^{-1} \bmod 998\,244\,353, where y−1y^{-1} is an integer such that y⋅y−1 mod 998 244 353=1y \cdot y^{-1} \bmod 998\,244\,353 = 1.

Hint

Explanation of the first example: There are three different blind boxes: (1,1)(1,1), (1,2)(1,2), and (2,2)(2,2). Their cashback amounts are 11, 22, and 44. So the minimum price is 73\frac{7}{3}.

The answer to the second example is 42525126=6752\frac{42525}{126} = \frac{675}{2}.

Examples2

  1. Example 1

    Input
    2 2
    
    Expected output
    332748120
    
  2. Example 2

    Input
    5 5
    
    Expected output
    499122514