2021 蓝桥杯热身赛 #2

果冻发现贤者禾枫有文学天赋，于是让她构造剧情线。对于某一章节，贤者一共想了 $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$ 取模后的结果。

样例

标准输入复制文本

标准输出复制文本

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

提交 43

通过 1

A B C D E F G H I J