#C20. [SDOI2016]排列计数

[SDOI2016]排列计数

题目描述

求有多少种 11nn 的排列 aa,满足序列恰好有 mm 个位置 ii,使得 ai=ia_i = i

答案对 109+710^9 + 7 取模。

输入格式

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

输入的第一行是一个整数 TT,代表测试数据的整数。

以下 TT 行,每行描述一组测试数据。

对于每组测试数据,每行输入两个整数,依次代表 nnmm

输出格式

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

5
1 0
1 1
5 2
100 50
10000 5000
0
1
20
578028887
60695423

提示

数据规模与约定

对于全部的测试点,保证 1T5×1051 \leq T \leq 5 \times 10^51n1061 \leq n \leq 10^60m1060 \leq m \leq 10^6