题目描述

求有多少种长度为 $\red n$ 的序列 $\red A$，满足以下条件：

$\red 1$、$\red{1 \sim n}$ 这 $\red n$ 个数在序列中各出现了一次。

$\red 2$、若第 $\red i$ 个数 $\red{A_i}$ 的值为 $\red i$，则称 $\red i$ 是稳定的，序列恰好有 $\red m$ 个数是稳定的。

由于满足条件的序列可能很多，所以请你将序列数对 $\red{10^9+7}$ 取模后输出。

输入格式

第一行一个数 $\red T$，表示有 $\red T$ 组数据。

接下来 $\red T$ 行，每行两个整数 $\red n$、$\red m$。

输出格式

输出 $\red T$ 行，每行一个整数，表示求出的序列数对 $\red{10^9+7}$ 取模后的值。

样例

输入样例

5
1 0
1 1
5 2
100 50
10000 5000

输出样例

0
1
20
578028887
60695423

提示

$\red{T\le 500000}$,

$\red{n\le 1000000}$,

$\red{m\le 1000000}$