题目描述

求有多少个长度为 $n$ 的排列 $p$，满足恰好有 $m$ 个位置 $i$，使得 $p_i=i$。

答案对 $10^9+7$ 取模。

输入格式

第一行一个数 $T$，表示有 $T$ 组数据。 接下来 $T$ 行，每行两个整数 $n,m$。

输出格式

输出 $T$ 行，每行一个数，表示求出的序列数

5
1 0
1 1
5 2
100 50
10000 5000

0
1
20
578028887
60695423

提示

$1\le n\le 10^6$,$0\le m\le 10^6$,$1\le T\le 5\times 10^5$

题目来源

SDOI 2016