配点 : 500 点
問題文
整数 N,K 被给出。
(,) 构成的正确括号序列 s 对应的 sukoa 定义如下。
- (
(\times c )+ ()\times c) 形式的字符串((),(()),((()))等...)被称为良好字符串。 s 中(不一定是连续的)子序列中包含的良好字符串的最大长度,s 称为该序列的 sukosa。
长度为 2N 的正确括号序列,其 sukoa 恰好变为 2K 的数量求对 998244353 取模的余数。
1 对于每一个输入,T 个测试用例需要求解。
正确的括号序列是
正确的括号序列是,() 删除其中的子字符串 0 若干次后能够变为空字符串的字符串。
制約
- 1 \leq T \leq 10^5
- 1 \leq K \leq N \leq 10^6
- 输入全部为整数
入力
输入是按以下格式从标准输入给出的。
T case_1 case_2 \vdots case_T
每个测试用例按以下形式给出。
N K
出力
输出答案。
入力例 1
4 2 1 2 2 3 1 100 70
出力例 1
1 1 0 366458221
长度为 4 的正确括号序列及其分数如下。
()(): 苏科亚 2(()): 苏科亚 4