问题 C: 简单的数学题
内存限制：128 MB
时间限制：2.500 S
评测方式：文本比较
命题人：
提交：35
解决：3
题目描述
在 1 到 $N$ 中选取 $K$ 个数，有多少种选法使得选出的数字总和是 $N$ 的倍数？
由于答案可能太大，请输出结果对 998244353 取模的结果。
由于答案可能太大，请输出结果对 998244353 取模的结果。
输入
本题包含多组数据。
输入的第一行为一个整数 $T (1 \leq T \leq 5)$，表示共有 $T$ 组测试数据。
接下来依次出现 $T$ 组测试数据，每组数据包含两个整数 $N, K (1\leq N \leq 10^{9}, 1 \leq K \leq \min(100, N))$。
对于所有的测试数据，保证 $\sum K \leq 100$，保证 $N \neq 998244353$。
输入的第一行为一个整数 $T (1 \leq T \leq 5)$，表示共有 $T$ 组测试数据。
接下来依次出现 $T$ 组测试数据，每组数据包含两个整数 $N, K (1\leq N \leq 10^{9}, 1 \leq K \leq \min(100, N))$。
对于所有的测试数据，保证 $\sum K \leq 100$，保证 $N \neq 998244353$。
输出
输出一个整数：在 1 到 $N$ 中选取 $K$ 个数，使得选出的数字总和是 $N$ 的倍数的方法数。对 998244353 取模。
样例输入 复制
4
10 1
10 2
6 4
114514 19样例输出 复制
1
4
3
579587762提示
样例解释如下：
第一组测试数据，只有 1 种选法能够从 $1$ 到 $10$ 中选 1 个数，使得和为 10 的倍数：
第二组测试数据，有以下 4 种选法能够从 $1$ 到 $10$ 中选 2 个数，使得和为 10 的倍数：
第三组测试数据，有以下 3 种选法能够从 $1$ 到 $6$ 中选 4 个数，使得和为 6 的倍数：
第一组测试数据，只有 1 种选法能够从 $1$ 到 $10$ 中选 1 个数，使得和为 10 的倍数：
- $10$
第二组测试数据，有以下 4 种选法能够从 $1$ 到 $10$ 中选 2 个数，使得和为 10 的倍数：
- $1 + 9 = 10$
- $2 + 8 = 10$
- $3 + 7 = 10$
- $4 + 6 = 10$
第三组测试数据，有以下 3 种选法能够从 $1$ 到 $6$ 中选 4 个数，使得和为 6 的倍数：
- $1 + 2 + 3 + 6 = 12$
- $1 + 2 + 4 + 5 = 12$
- $3 + 4 + 5 + 6 = 18$