F. Nice Positions

观察：对于一个序列，任意相邻两个数至少有一个是好的，即不存在两个连续的坏点

简单套个容斥就是

好点>=k的方案 <==> 坏点<=n-k的方案

然后从小到大把每个数插入排列，发现如果插入的数在一个坏点两侧，那么坏点数量不变，否则坏点数量+1

主要是一直在考虑，确定前i个点后再确定第i+1个点，从左往右依次确定的线性推法

但是如果从把最后一个数插入排列的任意位置的角度考虑就会简单很多

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define mem(x, y) memset(x, y, sizeof(x))
using namespace std;
const int N = 3e3 + 5, MOD = 1e9 + 7;
int add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }
int sub(int a, int b) { return a - b < 0 ? a - b + MOD : a - b; }
int mul(int a, int b) { return 1ll * a * b % MOD; }

int dp[N][N];

int sum[N][N];

int main() {
    dp[1][1] = 1;
    for (int i = 2; i <= 3000; i++) {
        for (int j = 0; j <= i; j++) {
            if (j <= i - 1) dp[i][j] = add(dp[i][j], mul(dp[i - 1][j], mul(j, 2)));
            if (j >= 1) dp[i][j] = add(dp[i][j], mul(dp[i - 1][j - 1], sub(i, mul(j - 1, 2))));
        }
    }
    for (int i = 1; i <= 3000; i++) {
        for (int j = 0; j <= i; j++) {
            sum[i][j] = dp[i][i - j];
        }
    }
    for (int i = 1; i <= 3000; i++) {
        for (int j = i - 1; j >= 0; j--) {
            sum[i][j] = add(sum[i][j], sum[i][j + 1]);
        }
    }
    int q; scanf("%d", &q);
    while(q--) {
        int u, v; scanf("%d %d", &u, &v);
        printf("%d\n", sum[u][v]);
    }
    return 0;
}