J-Subpermutation_牛客竞赛数学专题班简单排列和组合（排列组合问题、阶乘、组合数）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\ n$ 的排列是一个长度为 $\ n$ 的序列，其中从 $\ 1$ 到 $\ n$ 的每个数字都只出现一次。 $\ n$ 的全排列是将 $\ n$ 的所有排列按字典顺序连接成一个序列的序列。如果 $\ p_i<q_i$ 其中 $\ i$ 是满足 $p_i≠q_i$ 的最小索引，则序列 $p_1,p_2,...,p_n$ 在字典上小于 $\ q_1,q_2,...,q_n$ 。

以下是此问题中使用的一些符号：

- $\ p_n$ ： $\ n$ 的全排列。例如， $\ p_3=\{1,2,3,1,3,2,2,1,3,2,3,1,3,1,2,3,2,1\}$ 。
- $\ S_n$ ： $\ n$ 的所有排列的集合。例如， $\ S_3=\{\{1,2,3\},\{1,3,2\},\{2,1,3\},\{2,3,1\},\{3,1,2\},\{3,2 ,1\}\}$ 。
- $\ f(s,t)$ ： $\ s$ 中等于 $\ t$ 的连续子序列的数量。例如， $\ f(\{1,2,12,1,2\},\{1,2\})=2$ 。

现在给定 $\ n$ 和 $\ m$ ，请计算 $\ ∑_{t∈S_m}f(p_n,t)\ modulo\ 10^9+7$ 。

输入描述:

第一行包含一个整数，表示数据组数。
接下来行，每行包含两个整数 和，如描述中所述。

输出描述:

对于每组数据，输出。

示例1

输入

复制

输出

复制

说明

对于第三组数据，, 。 中有个连续子序列等于或：

备注:

原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=7133