Problem Description

X has recently been studying the derangement problem, so he started thinking about a variant: how many permutations $p$ of length $n$ satisfy that for positions $i \le m$, $p_i > m$, and for all positions $i$, $p_i \ne i$?

X came up with a total of $T$ such queries. Can you tell him the answer for each query?

Since the answer may be too large, you only need to output it modulo $998244353$.

Input Format

The first line contains an integer $T$, representing the number of queries.

The next $T$ lines each contain two integers $n, m$.

Output Format

Output $T$ lines, each containing one integer: the answer modulo $998244353$.

6
8 0
8 4
100 10
1000 100
10000 1000
100000 10000

14833
576
548326276
694205000
493811811
135068319

Hint

For 100% of the testdata, $0 \le T \le 2 \times 10^5$, $0 \le m \le n \le 2 \times 10^5$.

This problem uses bundled subtasks.

• Subtask 1 (1pts): $T = 0$.
• Subtask 2 (9pts): $T \le 10$, $n, m \le 8$.
• Subtask 3 (10pts): $m = 0$.
• Subtask 4 (20pts): $n, m \le 5000$.
• Subtask 5 (20pts): $T \le 10$.
• Subtask 6 (40pts): No special constraints.

Translated by ChatGPT 5