Blind Box
Time limit1sMemory limit512 MB
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 cards, and there is a positive integer written on each card. The cards in each box are ordered so that the number on the -th card is greater than or equal to the number on the -th card for every . The integer on each card does not exceed .
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 such that the numbers on the -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 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 and : the number of cards in each box and the maximum value on a card ().
Output
Print a single integer: the minimum price, modulo . The price may be a fraction. If the minimum price is the irreducible fraction , print , where is an integer such that .
Hint
Explanation of the first example: There are three different blind boxes: , , and . Their cashback amounts are , , and . So the minimum price is .
The answer to the second example is .