#562. 「LibreOJ Round #9」Tangjz 的背包

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: tangjz

题目描述

你有 n 个候选物品,你想要从中选出 m 个物品放进体积为 v 的背包里。

在选择物品时,你发现这些候选物品的体积分别为 1, 2, \cdots, n ,于是你想知道有多少种选法可以恰好将体积为 v 的背包填满。

注意,两种选法不同当且仅当存在至少一个候选物品只在某一种选法中被选择。

为了便于输出,我们假设从这样的 n 个候选物品里选出 m 个物品填满体积为 v 的背包有 f(v) 种选法,并令 p 为使得 f(p) 不为 0 的最大正整数,你只需要输出 \left(\sum\limits_{v = 1}^{p}{{19190506}^{p - v} f(v)}\right) \bmod 998244353 的值即可。显而易见的是当 1 \leq m \leq n 时一定存在这样的 p

输入格式

第一行包含一个正整数 T ,表示有 T 组测试数据。

接下来依次给出每组测试数据,每组测试数据仅两行,包含两个正整数 n m ,含义如题目所示。

输出格式

对于每组测试数据,输出一行,包含一个整数,表示题目中要求输出的值。

样例

样例输入 1

1
3 2

样例输出 1

238284724

样例解释 1

对于该组样例, f(3) = 1, f(4) = 1, f(5) = 1 ,其他 f(v) 都为 0 ,所以有 p = 5

样例输入 2

1
4 2

样例输出 2

186699913

样例解释 2

对于该组样例, f(3) = 1, f(4) = 1, f(5) = 2, f(6) = 1, f(7) = 1 ,其他 f(v) 都为 0 ,所以有 p = 7

数据范围与提示

对于所有数据, 1 \leq T \leq 5 \times 10^5, 1 \leq m \leq n \leq 10^{12}

子任务编号 分值 n\leq 特殊限制
1 10 5000
2 35 50000 不同的 n 至多有 10
3 20 10^6
4 35 10^{12}