小G的排列-加强版

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

题目描述

找出满足以下条件的排列 ${A=\{a_1,a_2,...,a_n\}}$ 的数量：
1. ${|A|=n}$
2. $1\le a_i\le n$
3. $\forall i\neq j,a_i\neq a_j(i,j\in[1,n])$

4. 若对于整数对 $l,r(1\le l\le r\le n)$ 满足：任意 ${i\in[l+1,r]}$ 都有 $|a_i-a_{i-1}|=1$ 。则必须满足 $r-l+1\le m$ 。

对答案 $\bmod 1e9+7$

输入包含组测试用例，第一行一个整数
接下来行每行两个整数

输出行，第行为第组测试用例的答案。

示例1

复制

复制