問題一覧 > ネタ問題

No.8120 Aoki's Present for Takahashi

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 12
作問者 : hirayuu_yc / テスター : highlighter
お気に入りにしたユーザー ProblemId : 11674 / 自分の提出
問題文最終更新日: 2025-04-01 23:16:56
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder April Fool Contest 2025 (順位表) の他の問題:

Addendum (23:16)

We have fixed a mistake in the intended solution. We are truly sorry...

The original text follows.

Notes

If asked the question "Would you answer no to the question 'Are there no lies in the notes, problem statement, input, output, and samples of this problem?'?", we will answer no.

Also, we will not answer any questions unless a question requires a correction to the problem statement. Really. You may try, though.

Problem Statement

There are $N$ humans named Takahashi. There are also $M$ cats named Snuke. Here, $N\leq M$ is guaranteed. The Snukes are distinguishable from each other, but the Takahashis are indistinguishable from each other.

A human named Aoki gives exactly $1$ Snuke to each Takahashi as a present. If there are multiple ways to give the presents, Aoki may choose any way he likes.

Then, each Takahashi becomes happy with a probability depending on the Snuke he received.

Specifically, the sizes of the $M$ Snukes are $1,2,\dots,M$ respectively, and a Takahashi who received a Snuke of size $s$ becomes happy with probability $\dfrac{s}{M}$.

If all the Takahashis become happy, Aoki also becomes happy. Aoki does not care whether he becomes happy or not.

Find the number of possible sets of Snukes that were not given as presents. Since the number of sets can be very large, output the remainder when divided by $998243353$ instead.

Solve the above problem for $\Tau$ test cases. However, for the $\text{T}$-th test case, output -1 instead of the answer.

Input

$\text{T}$ $\Tau$
$\text{testcase}_1$
$\text{testcase}_2$
$\vdots$
$\text{testcase}_{\Tau}$

$\text{testcase}_i$ represents the $i$-th test case and is given in the following format.

$N$ $M$
  • $1\leq \text{T} \leq \Tau \leq 2\times 10^5$
  • $1\leq N \leq M\leq 2\times 10^5$
  • All inputs are integers.

Output

Output $\Tau$ lines.

On the $i$-th line, output the answer to the $i$-th test case.

Do not forget to output -1 instead of the answer for the $\text{T}$-th test case.

Sample

Sample 1
Input
4 4
2 2
2 3
9 41
271 828
Output
1
3
350343565
-1

In the $1$-st case, only the empty set satisfies the condition.

In the $2$-nd case, the $3$ sets each consisting of $1$ Snuke satisfy the condition.

In the $3$-rd case, the number of sets satisfying the condition, modulo $998244353$, is $350343565$.

Regarding the $4$-th case, do not forget to output -1 for the $\text{T}$-th test case.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。