题目描述

求有多少种 $1$ 到 $n$ 的排列 $a$ ，满足序列恰好有 $m$ 个位置 $i$ ，使得 $a_i = i$ 。

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

输入格式

本题单测试点内有多组数据。

输入的第一行是一个整数 $T$ ，代表测试数据的整数。

以下 $T$ 行，每行描述一组测试数据。

对于每组测试数据，每行输入两个整数，依次代表 $n$ 和 $m$ 。

共输出 $T$ 行，对于每组测试数据，输出一行一个整数代表答案。

本题共 20 个测试点，各测试点等分，其数据规模如下表。

测试点编号	$T =$	$n, m \leq$	测试点编号	$T =$	$n, m \leq$
$1\sim 3$	$10^3$	$8$	$10 \sim 12$	$10^3$	$10^3$
$4 \sim 6$		$12$	$13 \sim 14$	$5 \times 10^5$	$10^3$
$7 \sim 9$		$100$	$15 \sim 20$	$5 \times 10^5$	$10^6$

对于全部的测试点，保证 $1 \leq T \leq 5 \times 10^5$ ， $1 \leq n \leq 10^6$ ， $0 \leq m \leq 10^6$ 。