TopCoder

餘切
$\Huge\text{pooh is 8}$

User's AC Ratio

90.0% (9/10)

Submission's AC Ratio

40.9% (9/22)

Tags

Description

對於一個有 $N$ 個正整數的陣列 $a$ 和一個區間 $[l,r]$ ,我們說 $[l,r]$ 是個好區間若且為若:

  • $1 \leq l < r \leq N$
  • $\forall l < i < r$,$a_l < a_i$
  • $\forall l < i < r$,$a_r < a_i$

也就是說,$a_{l+1}$ 到 $a_{r-1}$ 的數字全部比 $a_l$ 和 $a_r$ 大。

現在給你兩個正整數 $n,m$,請輸出滿足下列敘述的排列 $p$ 個數:

  • $p$ 是一個 $1$ 到 $n$ 的排列,代表所有 $1$ 到 $n$ 個數字都剛好出現在 $p$ 一次,且 $p$ 的長度為 $n$
  • $p$ 中總共有 $m$ 個好區間

由於這個數字可能很大,請輸出他模 $998244353$
本題有多筆測資,詳細說明請看 Input Format

Input Format

第一行有一個正整數 $t$,代表有幾筆測資
接下來 $t$ 行中,每行有兩個正整數 $n,m$,意義如題目所述

對於所有測試資料:

  • $1 \leq t \leq 10 ^ 6$
  • $1 \leq n \leq 3000$
  • $1 \leq m \leq 4498500$

Output Format

每行輸出一個整數,代表滿足題目要求的排列數模 $998244353$

Sample Input 1

4
3 2
8 10
10 45
11 18

Sample Output 1

4
11760
0
4106304

Hints

例:$[1, 3, 2]$ 為一個長度為 $3$ 的排列,且他總共有 $3$ 個好區間,分別是 $[1,3]$、$[1,3,2]$ 跟 $[3, 2]$

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 1 $n = 8$ 15
3 2 $m = n - 1$ 22
4 0, 3~9 $t \leq 5$ 31
5 0~31 無特別限制 32

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 262144 65536 1 4 5
1 2000 262144 65536 2 5
2 2000 262144 65536 3 5
3 2000 262144 65536 4 5
4 2000 262144 65536 4 5
5 2000 262144 65536 4 5
6 2000 262144 65536 4 5
7 2000 262144 65536 4 5
8 2000 262144 65536 4 5
9 2000 262144 65536 4 5
10 2000 262144 65536 5
11 2000 262144 65536 5
12 2000 262144 65536 5
13 2000 262144 65536 5
14 2000 262144 65536 5
15 2000 262144 65536 5
16 2000 262144 65536 5
17 2000 262144 65536 5
18 2000 262144 65536 5
19 2000 262144 65536 5
20 2000 262144 65536 5
21 2000 262144 65536 5
22 2000 262144 65536 5
23 2000 262144 65536 5
24 2000 262144 65536 5
25 2000 262144 65536 5
26 2000 262144 65536 5
27 2000 262144 65536 5
28 2000 262144 65536 5
29 2000 262144 65536 5
30 2000 262144 65536 5
31 2000 262144 65536 5