问题 J: 网格计数

内存限制:524 MB 时间限制:2 S
题面:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

给定整数 $ m $ 和 $ n $,计算在一个 $ m \times m $ 网格中选择 $ n $ 个点的方案数,满足:
- 路径由 $ n $ 个点 $\left(x_1, y_1\right), \left(x_2, y_2\right), \cdots, \left(x_n, y_n\right)$ 组成,其中 $ x_i, y_i \in \\{1, 2, \dots, m\\} $。
- 横坐标严格递增:$ x_1 < x_2 < \dots < x_n $。
- 纵坐标严格递增:$ y_1 < y_2 < \dots < y_n $。
- 每个点满足 $ x_i < y_i $。
答案可能很大,输出方案总数对 $ 998244353 $ 取模的结果。
两条路径不同,当且仅当它们的点序列 $\left(x_1, y_1\right), \left(x_2, y_2\right), \cdots, \left(x_n, y_n\right)$ 在至少一个位置 $ i $ 上有不同的坐标(即 $ x_i \neq x_i' $ 或 $ y_i \neq y_i' $)。
---
为了防止输入过大带来的常数问题,C++ 选手请尽量使用关闭流同步的 `std::cin` 和 `std::cout` 实现输入输出,否则可能出现因读入输出问题导致的 TLE 等。
```cpp
int main(){
std::ios::sync_with_stdio(0);
std::cin.tie(0);
// your code
return 0;
}
```
 

输入格式

第一行一个整数 $ T $ $\left(1 \leq T \leq 2\times 10^5\right) $,表示测试数据组数。
每组数据的第一行包含两个整数 $ m $ 和 $ n $ $\left(1\leq n\leq m\leq 2\times 10^5\right)$,表示网格大小和路径点数。
 

输出格式

对于每组数据,输出一行一个整数,表示满足条件的路径总数对 $998244353$ 取模的结果。
 

输入样例 复制

5
4 2
5 3
500 250
100 34
100000 35546

输出样例 复制

6
10
534807094
413150436
987694527