新年快乐 。゚・ (⁄ ⁄>⁄ ︿ ⁄<⁄ ⁄) ・゚。

1621. 异世界的剧情分支(15分)

果冻发现贤者禾枫有文学天赋,于是让她构造剧情线。对于某一章节,贤者一共想了 m 个有区别的剧情分支和 n 个无区别的剧情背景。现要求每个剧情分支必须选择至少一个剧情背景作为基础,且要求每个背景必须被唯一的剧情分支选择。求有多少种剧情背景的选择方案。

输入

首先输入一行一个整数 t ,代表询问的个数。

接下来输入 t 行,每行两个整数,代表 n,m ,用一个空格隔开。

20\% 分数的数据,1\le n,m\le8

40\% 分数的数据,1\le n,m\le10^3

80\% 分数的数据,1\le n,m\le9\times10^4

100\% 分数的数据,1\le n,m\le10^{18},m\le n,1\le t\le10^5

输出

输出 t 行,每行一个整数,代表每个询问的选择方案数对质数 99991 取模后的结果。

样例

标准输入 复制文本
3
5 5
5 2
5 3
标准输出 复制文本
1
4
6

提示

n=m=5 ,只有一种方案:每个分支选一个背景

n=5,m=2 ,可以让两个分支分别选 (1,4),(2,3),(3,2),(4,1) 个背景,共四种方案

n=5,m=3 ,可以让三个分支分别选 (1,1,3),(1,3,1),(3,1,1),(1,2,2),(2,1,2),(2,2,1) 个背景,共六种方案

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 146
通过 15