#XMOJ12268. 监考

监考

说明

时间限制:1 Sec 内存限制:256 MB 输入文件:invigilate.in 输出文件:invigilate.out

一位老师(匿名)在附近正在举办节分祭的时候,监考期末考试时想出了下面这道题。


为了防止作弊,考生不能坐在同一张桌子上相邻的椅子。

例如,一张桌子共有 $3$ 把椅子:如果坐 $2$ 名考生,则只能选择两端的椅子;如果只坐 $1$ 名考生,则可以任选 $3$ 把椅子中的任意一把。


在一间特殊房间里只有一张桌子,一共有 $C$ 把椅子。

现在有 $P$ 名考生在这个房间参加考试,请你求出考生的座位安排方案数,答案对 $10^9+7$ 取模。

输入格式

第一行一个整数 $T$,代表测试用例数量。

每组测试用例单独一行,包含两个整数 $C,P$。

输出格式

对每组测试用例,输出考生座位安排方案数,对 $10^9+7$ 取模。

样例

样例 1

3
3 2
1 196547891657825679231564789567843659723659763246578365879364576378658372657842658746758638746587236589762187456587168
123456789 1

2
0
123456789

样例说明:

第 11 组:22 名考生只能坐在两把端点椅子。两个人交换位置算作不同方案,共 22 种。

第 $2$ 组:不可能安排,答案为 $0$。

第 $3$ 组:可以任选一把椅子坐下。

数据范围

对于 30% 的数据,$C,P \le 10^9$。

对于 60% 的数据,$C \le 10^{18}$,$P \le 10^9$。

对于 100% 的数据,满足 $1 \leq T \leq 30$,$1 \leq C \leq 10^{10000}$,$1 \leq P \leq 10^{10000}$。

提示

代码大小限制为 64KB。