排列

时间限制：$1s$

空间限制：$256MB$

题目描述

对于$n$，连接所有n的排列生成序列$S$，例如$n=3$，则$S={1,2,3,1,3,2,2,1,3,2,3,1,3,1,2,3,2,1}$，对于给定的$m$，你需要找出$S$中有多少个连续的长度为$m$的子串，满足该子串是$m$的排列。答案对$1e9+7$取模。

数据格式

输入

第$1$行$1$个整数，表示询问数量。

接下来 $T$ 行，每行$2$个整数，表示$n,m$。

输出

输出 $T$ 行，给出$S$中$m$排列数量。

样例

输入1

1
4 2

输出1

14

输入2

5
10 9
8 7
6 5
4 3
2 1

输出2

3005271
31661
515
15
2

数据范围及约定

$1≤m≤n≤10^5,1≤T≤10^5$。