笔刷

题目描述

现在有一张长度为 $h$ 的画布，下标 $0\sim h-1$，你需要用笔刷将其染上颜色。

笔刷可以表示为一个长度为 $n-1$ 的正整数序列 $d_1,d_2,\dots,d_{n-1}$。每次可以选择画布的 $n$ 个位置 $b_1\sim b_n$ 满足：

并将画布的这 $n$ 个位置染上色。

由于颜色太深太浅都不好看，所以画布的每一个位置都必须恰好被染色一次。一支笔刷是合格的，当且仅当存在一种方法，能够恰好将画布的每一个位置都染色一次；两支笔刷不同，当且仅当 $\{d_{n-1}\}$ 中至少有一个位置不同。

共 $T$ 组数据，每次给出 $h,n$，请计数对于固定的 $h,n$，有多少支合格的笔刷，答案对 $10^9+7$ 取模。

输入格式

输入包括若干行。

第一行包含一个整数 $T$。接下来 $T$ 行，每行包括两个整数 $h,n$，表示一组数据。

输出格式

输出包括 $T$ 行，每行包含一个整数，表示合格的笔刷个数。

样例

4
9 3
1 1
100 10
5 4

2
1
14
0

样例解释

对第一组数据，仅有笔刷 $\{1,1\}$ 和 $\{3,3\}$ 满足条件。

数据范围

• 对于 30% 的数据：$T=5$，$1\le n\le 3$，$1\le h\le 100$。
• 对于 60% 的数据：$T=10$，$1\le n\le h\le 10^5$。
• 对于 100% 的数据：$T=500$，$1\le n\le h\le 10^9$。